\[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)\]
.