Solution of Linear Congruence

Theorem

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

The following results hold:

• It has solutions iff $\gcd \left\{{a, n}\right\} \backslash b$ (that is, iff $\gcd \left\{{a, n}\right\}$ is a divisor of $b$)
• If $\gcd \left\{{a, n}\right\} = 1$, the congruence has a unique solution
• If $\gcd \left\{{a, n}\right\} = d$, the congruence 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 \pmod {\dfrac n d}$

Proof

Consider the linear congruence $a x \equiv b \pmod n$.

Suppose $\exists x_0 \in \Z: a x_0 \equiv b \pmod n$.

Then $\exists y_0 \in Z: a x_0 - b = n y_0$ by definition of congruence.

Thus $x = x_0, y = y_0$ is a solution to the linear Diophantine equation $ax - ny = b$.

On the other hand, if $x = x_0, y = y_0$ is a solution to the linear Diophantine equation $ax - ny = b$, then it follows that $a x \equiv b \pmod n$.

Hence the problem of finding all integers satisfying the linear congruence $a x \equiv b \pmod n$ is the same problem as finding all the $x$ values in the linear Diophantine equation $ax - ny = b$.

Hence the following:

• It has solutions iff $\gcd \left\{{a, n}\right\} \backslash b$:

This follows directly from Solution of Linear Diophantine Equation: the linear Diophantine equation $ax - ny = b$ has solutions iff $\gcd \left\{{a, n}\right\} \backslash b$.

• If $\gcd \left\{{a, n}\right\} = 1$, the congruence has a unique solution:

Suppose then that $\gcd \left\{{a, n}\right\} = 1$.

From Solution of Linear Diophantine Equation, if $x = x_0, y = y_0$ is one solution to the linear Diophantine equation $ax - ny = b$, the general solution is:

$\forall k \in \Z: x = x_0 + n k, y = y_0 + a k$

But $\forall k \in \Z: x_0 + n k \equiv x_0 \pmod n$.

Hence $x \equiv x_0 \pmod n$ is the only solution of $a x \equiv b \pmod n$.

• If $\gcd \left\{{a, n}\right\} = d$, the congruence 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 \pmod {\dfrac n d}$:

But $\gcd \left\{{\dfrac a d, \dfrac n d}\right\} = 1$ from Divide by GCD for Coprime Integers.

So the RHS has a unique solution modulo $\dfrac n d$, say:

$x \equiv x_1 \pmod {\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 $\left\{{x_1, x_1 + \dfrac n d, x_1 + 2 \dfrac n d, \ldots, x_1 + \left({d-1}\right)\dfrac n d}\right\}$.

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:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x_1 + k \frac n d\)	\(=\)	\(\displaystyle x_1 + \left({d q + r}\right) \frac n d\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle x_1 + n q + r \frac n d\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle x_1 + r \frac n d\)	\(\displaystyle \)	\(\displaystyle \pmod n\)	\(\displaystyle \)

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

$\blacksquare$