Solution of Linear Congruence

Theorem

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

The following results hold:

Existence

$a x \equiv b \pmod n$ has at least one solution if and only if:

$\gcd \set {a, n} \divides b$

that is, if and only if $\gcd \set {a, n}$ is a divisor of $b$.

Condition for Uniqueness

$a x \equiv b \pmod n$ has a unique solution if and only if $\gcd \set {a, n} = 1$.

Number of Solutions

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}$

Examples

Solution to $5 x = 4 \pmod 3$

Let $5 x = 4 \pmod 3$.

Then:

$x = 2 + 3 u$

where $u \in \Z$.

Solution to $7 x = 6 \pmod 5$

Let $7 x = 6 \pmod 5$.

Then:

$x = 3 + 5 u$

where $u \in \Z$.

Solution to $9 x = 8 \pmod 7$

Let $9 x = 8 \pmod 7$.

Then:

$x = 4 + 7 t$

where $t \in \Z$.