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