Solution of Linear Congruence/Number of Solutions

Theorem

Let $a x \equiv b \pmod n$ be a linear congruence.

Let $\gcd \set {a, n} = d$.

Then $a x \equiv b \pmod n$ has $d$ solutions which are given by the unique solution modulo $\dfrac n d$ of the congruence:

$\dfrac a d x \equiv \dfrac b d \paren {\bmod \dfrac n d}$

the problem of finding all integers satisfying the linear congruence $a x \equiv b \pmod n$

is the same problem as:

the problem of finding all the $x$ values in the linear Diophantine equation $a x - n y = b$.

$\gcd \set {\dfrac a d, \dfrac n d} = 1$

So the right hand side has a unique solution modulo $\dfrac n d$, say:

$x \equiv x_1 \paren {\bmod \dfrac n d}$

So the integers $x$ which satisfy $a x \equiv b \pmod n$ are exactly those of the form $x = x_1 + k \dfrac n d$ for some $k \in \Z$.

Consider the set of integers:

$\set {x_1, x_1 + \dfrac n d, x_1 + 2 \dfrac n d, \ldots, x_1 + \paren {d - 1} \dfrac n d}$

None of these are congruent modulo $n$ and none differ by as much as $n$.

Further, for any $k \in Z$, we have that $x_1 + k \dfrac n d$ is congruent modulo $n$ to one of them.

To see this, write $k = d q + r$ where $0 \le r < d$ from the Division Theorem.

Then:

$\ds x_1 + k \frac n d$

$=$

$\ds x_1 + \paren {d q + r} \frac n d$

$\ds $

$=$

$\ds x_1 + n q + r \frac n d$

$\ds $

$\equiv$

$\ds x_1 + r \frac n d$

$\ds \pmod n$

So these are the $d$ solutions of $a x \equiv b \pmod n$.

$\blacksquare$