## Solutions of Linear Congruences

Theorem
Consider the linear congruence
$ax \equiv b \; (mod \; n)$

a) The congruence has solutions if and only if
$gcd(a, n) | b$

b) If
$gcd(a,n)-1$
the congruence has a unique solution.
c) If
$gcd(a,n)-d$
and
$d | b$
the congruence has
$d$
solutions which can be found from the unique solution
$mod \frac{n}{d}$
of the congruence
$ax \equiv b \; (mod \; \frac{n}{d})$
.
Proof
a) The linear Diophantime
$ax-ny=b$
has solutions if and only if
$gcd(a,n) | b$
. Hence the linear congruence has solutions if and only if
$gcd(a, n) | b$

b) Suppose
$gcd(a,n)=1$
then if
$x_0, \; y_0$
are solutions of
$ax-ny=b$
then the general solution is
$x_0+nk, \; y_0+ak, \; k \in \mathbb{Z}$
.
For all integers
$k \in \mathbb{Z}$

$x_0+nk \equiv x_0 \; (mod \; n)$
so
$x_0$
is the only solution of
$ax \equiv b \; (mod \; n)$
.
c) If
$gcd(a,n)=d, \; d | b$
then
$ax \equiv b \; (mod \; n) \leftrightarrow \frac{a}{d} \equiv \frac{b}{d} \; (mod \; \frac{n}{d})$
.
But
$gcd( \frac{a}{d}, \frac{n}{d})=1$
so the right hand congruence has a unique solution
$mod \; n$
, say
$x_1$
.
Hence the integers which satisfy
$ax \equiv b \; (mod \; n)$
are precisely those of the form
$x=x_1+ k \frac{n}{d}$
for some integer
$k$
.
Consider the set
$\{ x_1, \; x_1 + \frac{n}{d}, \; x_1+2 \frac{n}{d},...,x_1+(d-1) \frac{n}{d} \}$
. No two members of the set are congruent
$mod \; n$
. Any integer
$x_1 + k \frac{n}{d}$
is congruent
$mod \; n$
to some member of
$S$
because if we write
$n=dq+r$
then
$x_1+k \frac{n}{d} = x_1 +k (dq+r) \frac{n}{d}=x_1+nq+r \frac{n}{d} \equiv x_1+ \frac{r}{d} \; (mod \; n)$
.
Elements of
$S$
are then the solutions of
$ax \equiv b \; (mod \; n)$
.
Example: Solve the linear congruence
$30x \equiv 15 \; (mod \; 33)$
.
$gcd(15, 33)=3$
and
$3 | 33$
so there are 3 distinct solutions
$mod \; 33$
b y the above theorem. Cancel 3 to give
$10x \equiv 5 \; (mod \; 11)$
. Since
$gcd)10,11)=1$
so there is a unique solution
$mod \; 11$
, The Cancellation Rule allows us to cancel 5 to obtain
$2x \equiv 1 \; (mod \; 11)$
which is equivalent to
$2x \equiv 11 \; (mod \; 11)$
and we get
$x \equiv 6 \; (mod \; 11)$
. Other solutions are obtained by adding or subtracting multiples of
$\frac{33}{3}=11$
. We obtain
$x \equiv 6, \; 17, \; 28 \; (mod \; 11)$
. 