Linear Congruences
A linear congruence is the modular cousin of a linear equation:
ax \equiv b \pmod{n}.
We want all x (as residue classes mod n)
that satisfy it. This is the same problem as a
linear Diophantine equation
in disguise, so the same gcd condition decides everything.
The coprime case: just invert
When \gcd(a, n) = 1, the
inverse
a^{-1} exists, and the congruence has exactly one
solution — multiply both sides by it:
ax \equiv b \;\Longrightarrow\; x \equiv a^{-1} b \pmod{n}.
For instance 3x \equiv 4 \pmod 7: since
3^{-1} \equiv 5, we get
x \equiv 5 \cdot 4 = 20 \equiv 6 \pmod 7.
The general case
Let d = \gcd(a, n). Then ax \equiv b \pmod n:
- has no solution if d \nmid b;
- has exactly d solutions modulo n if d \mid b.
When d \mid b, divide the whole congruence through by
d to get a coprime one,
\tfrac{a}{d}x \equiv \tfrac{b}{d} \pmod{n/d}, solve that uniquely, then
the d solutions mod n are spaced
n/d apart. So 4x \equiv 6 \pmod{10} (with
d = 2) has the two solutions x \equiv 4, 9.
Why it matters
Linear congruences are the workhorses of modular problem-solving: solving them simultaneously,
for different moduli, is exactly the
Chinese Remainder Theorem,
and they appear whenever you must "undo" a multiplication in a finite system — from calendar
calculations to decoding.