How Many Solutions for a Congruence

How many solutions  
\[\]
  are possible for the linear congruence  
\[ax \equiv b \; (mod \; 20)\]
?
The congruence  
\[ax \equiv b \; (mod \; 20)\]
  has a unique solution modulo 20 if and only if  
\[gcd(a,20)=1\]
, when  
\[a \equiv 1, \; 3, \; 7, \; 9, \; 11, \; 13, \; 17, \; 19\]
. Each of these 8 possible values of  
\[a\]
  there are 20 possible values of  
\[b\]
  so there are 160 congruences for which the solution is unique modulo 20.
\[gcd(a,20)=2\]
  when  
\[a=2, \; 6, \; 14, \; 18\]
. Each congruence has solutions if and only if 2 divides  
\[b\]
  so  
\[b =0, \; 2, \; 4, \; 6, \; 8, \; 10, \; 12, \; 14, \; 16, \; 18\]
. This results in a further 40 possible congruences.
\[gcd(a,20)=4\]
  when  
\[a=4, \; 8, \; 12, \; 16\]
. Each congruence has solutions if and only if 4 divides  
\[b\]
  so  
\[b =0, \; 4, \; 8, \; 12, \; 16, \; 18\]
. Thi s results in a further 20 possible congruences.
\[gcd(a,20)=5\]
  when  
\[a=5, \; 15\]
. Each congruence has solutions if and only if 5 divides  
\[b\]
  so  
\[b =0, \; 5, \; 10, \; 15\]
. Thi s results in a further 8 possible congruences.
\[gcd(a,20)=10\]
  when  
\[a=10\]
. Each congruence has solutions if and only if 10 divides  
\[b\]
  so  
\[b =0, \; 10\]
. Thi s results in a further 20 possible congruences.
There are 160+40+20+8+2=230 possible solvable congruences.

You have no rights to post comments