Difference between revisions of "Linear congruence"
m |
|||
| Line 13: | Line 13: | ||
<math>5x\equiv 7\equiv 15\pmod{8}</math>, so | <math>5x\equiv 7\equiv 15\pmod{8}</math>, so | ||
| + | |||
| + | <math>x \equiv 3 \pmod 8</math>. Note that we can divide by 5 because 5 and 8 are [[relatively prime]]. | ||
| + | |||
| + | An alternative method is to note that | ||
| + | <math>5x\equiv 7 \pmod{8}</math>, so | ||
<math>5\cdot5x\equiv 5\cdot7\pmod{8}</math> and thus | <math>5\cdot5x\equiv 5\cdot7\pmod{8}</math> and thus | ||
<math>x \equiv 3 \pmod 8</math>. | <math>x \equiv 3 \pmod 8</math>. | ||
| + | |||
Note that not every linear congruence has a solution. For instance, the congruence equation | 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 | + | <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. | * if <math>d</math> does not divide <math>b</math>, there will be no solution. | ||
Revision as of 10:50, 15 August 2006
A Linear Congruence is a congruence mod p of the form
where 
, and 
are constants and 
is the variable to be solved for.
Example I: How to solve
Say 
. Find .
Solution
, so
. Note that we can divide by 5 because 5 and 8 are relatively prime.
An alternative method is to note that
, so
and thus
.
Note that not every linear congruence has a solution. For instance, the congruence equation
has no solutions. A solution is guaranteed if and only if 
is relatively prime to . If and are not relatively prime, say with greatest common divisor 
, then we have two options:
- if
divides 
, there will be a solution 
- if does not divide , there will be no solution.
, there will be a solution 
