Difference between revisions of "Linear congruence"

Revision as of 00:10, 15 November 2007

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.

Example I: How to solve

Say $5x\equiv 7\pmod{8}$ . Find $x$ .

Solution

$5x\equiv 7\equiv 15\pmod{8}$ , so

$x \equiv 3 \pmod 8$ . Note that we can divide by 5 because 5 and 8 are relatively prime.

An alternative method is to note that $5\cdot 5 \equiv 25 \equiv 1 \pmod{8}$ , so

$5\cdot5x\equiv 5\cdot7\pmod{8}$ and thus

$x \equiv 3 \pmod 8$ .

Note that not every linear congruence has a solution. For instance, the congruence equation $2x \equiv 3 \pmod 8$ has no solutions. A solution is guaranteed if and only if $a$ is relatively prime to $p$ . If $a$ and $p$ are not relatively prime, say with greatest common divisor $d$ , then we have two options:

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

@@ Line 27: / Line 27: @@
 Note that not every linear congruence has a solution.  For instance, the congruence equation
 <math>2x \equiv 3 \pmod 8</math> has no solutions.  A solution is guaranteed if and only if <math>a</math> is relatively prime to <math>p</math>.  If <math>a</math> and <math>p</math> are not relatively prime, say with [[greatest common divisor]] <math>d</math>, then we have two options:
-* if <math>d</math> [[divide]]s <math>b</math>, there will be a solution <math>\pmod \frac{p}{d}</math>
+* if <math>d</math> [[divide]]s <math>b</math>, there will be a solution <math>\pmod{ \frac{p}{d}}</math>
 * if <math>d</math> does not divide <math>b</math>, there will be no solution.

Page

Toolbox

Search

Difference between revisions of "Linear congruence"

Revision as of 00:10, 15 November 2007

Example I: How to solve

Solution