Linear Congruences

A linear congruence $ax \equiv b \pmod{n}$ is the mod-$n$ version of $ax = b$. It is really a linear Diophantine equation in disguise, $ax - ny = b$, so we already know when it can be solved. With inverses we can solve it quickly and count its solutions.

Theorem. Let $d = \gcd(a, n)$. The congruence $ax \equiv b \pmod{n}$ has a solution exactly when $d \mid b$. In that case it has exactly $d$ solutions mod $n$: if $x_0$ solves $$\frac{a}{d}\,x \equiv \frac{b}{d} \pmod{\frac{n}{d}},$$ then the solutions mod $n$ are $x_0,\ x_0 + \frac{n}{d},\ x_0 + 2\frac{n}{d},\ \dots,\ x_0 + (d - 1)\frac{n}{d}$.

Why it works

If $d \nmid b$: $ax - ny$ is always a multiple of $d$, so it never equals $b$. If $d \mid b$: $n \mid (ax - b)$ exactly when $\frac{n}{d} \mid \left(\frac{a}{d}x - \frac{b}{d}\right)$, so the two congruences have the same solutions. Since $\gcd\left(\frac{a}{d}, \frac{n}{d}\right) = 1$, the reduced one has an inverse and a single solution $x_0$ mod $\frac{n}{d}$. That one class mod $\frac{n}{d}$ splits into $d$ classes mod $n$, the ones listed.

The picture behind the count: the map $x \mapsto ax \bmod n$ hits only the multiples of $d$, and it hits each of them exactly $d$ times, because $ax \equiv ax' \pmod{n}$ exactly when $x \equiv x' \pmod{n/d}$. So a right side $b$ is hit $d$ times or not at all.

Arrows from $x$ to $4x \bmod 12$. Four arrows land on 8, so $4x \equiv 8$ has four solutions, spaced $12/4 = 3$ apart. Nothing lands on 6, because $\gcd(4, 12) = 4$ does not divide 6.

Worked example: One solution

Solve $7x \equiv 3 \pmod{12}$.

$\gcd(7, 12) = 1$, so there is exactly one solution mod 12.
$7^{-1} \equiv 7 \pmod{12}$, since $49 = 4 \cdot 12 + 1$.
$x \equiv 7 \cdot 3 = 21 \equiv 9$. Check: $7 \cdot 9 = 63 = 5 \cdot 12 + 3$.

Answer: $x \equiv 9 \pmod{12}$.

Worked example: Several solutions

Solve $10x \equiv 6 \pmod{14}$.

$d = \gcd(10, 14) = 2$ and $2 \mid 6$, so there are two solutions mod 14.
Divide $a$, $b$ and $n$ by 2: $5x \equiv 3 \pmod{7}$.
$5^{-1} \equiv 3 \pmod{7}$ (since $15 \equiv 1$), so $x \equiv 9 \equiv 2 \pmod{7}$.
Mod 14: $x \equiv 2$ or $2 + 7 = 9$. Check: $10 \cdot 9 = 90 = 6 \cdot 14 + 6$.

Answer: $x \equiv 2$ or $9 \pmod{14}$.

Worked example: No solution

Solve $6x \equiv 7 \pmod{15}$.

$\gcd(6, 15) = 3$, and $3 \nmid 7$.
$6x - 15y$ is always a multiple of 3, so it is never 7.

Answer: No solution.

Common mistake

Giving one solution when there are $d$ of them, or dividing $a$ and $b$ by $d$ but not $n$. In $10x \equiv 6 \pmod{14}$, the answer "$x \equiv 2$" misses $x \equiv 9$; and "$5x \equiv 3 \pmod{14}$" is a different congruence, whose only solution is $x \equiv 9$, so $x \equiv 2$ would be lost. Divide all three numbers, then list the $d$ solutions spaced $n/d$ apart, and check one by substitution.

Key idea

$ax \equiv b \pmod{n}$ is solvable exactly when $d = \gcd(a, n)$ divides $b$; then divide $a$, $b$ and $n$ by $d$, solve with an inverse, and you get $d$ solutions mod $n$, spaced $n/d$ apart.

Linear Congruences

Practice

Builds on

Leads to

Sources and further reading