## Solution of Linear Congruence

If
$gcd(a,n)=1$
then
$a^{\phi (n)} \equiv 1 \; (mod \; n)$
where
$\phi (n)$
is the number of integers between 1 and
$n$
relatively prime to
$n$
.
Using this fact we can solve the congruence
$ax \equiv b \; (mod \; n)$
.
$a^{\phi (n) -1}ax =a^{\phi (n)}x \equiv 1 x= a^{\phi (n) -1}b \; (mod \; n)$
.
For example, the linear congruence
$5x \equiv 11 \; (mod \; 12)$
has solution
$x \equiv 5^{\phi (12)-1} \times 11 \equiv 5^{3} \times 11 \; (mod \; 12) \equiv 5 \times 11 \; (mod \; 12) \equiv 7 \; (mod \; 13)$
.