Linear congruence
From AoPSWiki
A Linear Congruence is a congruence mod p of the form
where 
, 
, 
, and 
are constants and 
is the variable to be solved for.
Contents |
Solving
Note that not every linear congruence has a solution. For instance, the congruence equation 
has no solutions. A solution is guaranteed iff is relatively prime to . If and are not relatively prime, let their greatest common divisor be 
; then:
- if divides , there will be a solution
- if does not divide , there will be no solution
Example
Problem
Given 
, find .
Solution 1
, so 
. Thus, 
. Note that we can divide by 
because and 
are relatively prime.
Solution 2
Multiply both sides of the congruence by to get 
. Since 
and 
, 
.
