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