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

You have no rights to post comments