## How Many Solutions for a Congruence

\[\]

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.