## 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.