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.