Difference between revisions of "Linear congruence"

Revision as of 12:10, 14 July 2021

A Linear Congruence is a congruence mod p of the form $ax+b\equiv c\pmod{p}$ where $a$ , $b$ , $c$ , and $p$ are constants and $x$ is the variable to be solved for.

Solving

Note that not every linear congruence has a solution. For instance, the congruence equation $2x\equiv3\pmod8$ has no solutions. A solution is guaranteed iff $a$ is relatively prime to $p$ . If $a$ and $p$ are not relatively prime, let their greatest common divisor be $d$ ; then:

if $d$ divides $b$ , there will be a solution $\pmod{\frac{p}{d}}$
if $d$ does not divide $b$ , there will be no solution

Example

Problem

Given $5x\equiv7\pmod8$ , find $x$ .

Solution 1

$7\equiv15\pmod8$ , so $5x\equiv15\pmod8$ . Thus, $x\equiv3\pmod 8$ . Note that we can divide by $5$ because $5$ and $8$ are relatively prime.

Solution 2

Multiply both sides of the congruence by $5$ to get $25x\equiv35\pmod8$ . Since $25\equiv1\pmod8$ and $35\equiv3\pmod8$ , $x\equiv3\pmod8$ .

Revision as of 00:08, 19 December 2009 (view source) Just Beginner (talk \| contribs) (→‎Solution 1) ← Older edit		Revision as of 12:10, 14 July 2021 (view source) Etmetalakret (talk \| contribs) Newer edit →
Line 18:		Line 18:
	Multiply both sides of the congruence by <math>5</math> to get <math>25x\equiv35\pmod8</math>. Since <math>25\equiv1\pmod8</math> and <math>35\equiv3\pmod8</math>, <math>x\equiv3\pmod8</math>.		Multiply both sides of the congruence by <math>5</math> to get <math>25x\equiv35\pmod8</math>. Since <math>25\equiv1\pmod8</math> and <math>35\equiv3\pmod8</math>, <math>x\equiv3\pmod8</math>.

−	[[Category:~~Algebra~~]]	+	[[Category:Number Theory]]

Page

Toolbox

Search