Congruences and Applications

Putting Modular Arithmetic to Work

Modular arithmetic is not just theory — it powers check digits, hashing, calendars, and cryptography. This lesson develops the tools to solve modular equations and see where they apply.

A linear congruence has the form $ax \equiv b \pmod{n}$ — solve for the unknown residue $x$. The key is the multiplicative inverse: $a^{-1}$ is a residue with $a \cdot a^{-1} \equiv 1 \pmod n$. When it exists, multiply both sides by it to get $x \equiv a^{-1} b$. The crucial fact from Lesson 4: $a$ has an inverse mod $n$ if and only if $\gcd(a, n) = 1$ (they are coprime). So $ax \equiv b \pmod n$ has a unique solution exactly when $a$ and $n$ are coprime; otherwise it may have several solutions or none.

Two celebrated theorems make computation easy:

• Fermat's little theorem — if $p$ is prime and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod p$. This gives inverses ($a^{-1} \equiv a^{p-2}$) and fast primality tests.
• The Chinese remainder theorem — a system of congruences with coprime moduli has a unique solution modulo the product of the moduli, letting you reassemble a number from its remainders.

Applications are everywhere. Check digits (ISBN, credit cards) append a digit making a weighted sum $\equiv 0 \pmod{n}$, so single-digit errors are caught. Hash functions reduce keys mod a table size. And public-key cryptography (RSA) rests entirely on modular exponentiation being easy while its inverse (factoring, or the discrete logarithm) is hard — the coprimality and inverse ideas of this unit, scaled to enormous numbers.

Common pitfall: trying to solve $ax \equiv b \pmod n$ by "dividing by $a$" when $a$ and $n$ are not coprime. The inverse $a^{-1}$ exists only when $\gcd(a, n) = 1$; without it you cannot simply divide. When $\gcd(a, n) > 1$ the congruence has either no solution or several (never a single unique one) — checking coprimality first tells you which case you are in.