Linear congruence
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.