Congruences and Applications

Solving Congruences

Modular arithmetic powers check digits, hashing, calendars, and cryptography. A linear congruence has the form $ax \equiv b \pmod{n}$, solved for the unknown residue $x$.

The key tool is the multiplicative inverse: $a^{-1}$ is a residue satisfying $a \cdot a^{-1} \equiv 1 \pmod n$. Multiplying both sides by it yields $x \equiv a^{-1} b$.

$a$ has an inverse mod $n$ if and only if $\gcd(a, n) = 1$ (coprime). Thus, $ax \equiv b \pmod n$ has a unique solution when coprime; otherwise it yields several or none.

Common pitfall: Never "divide by $a$" when $a$ and $n$ are not coprime. The inverse $a^{-1}$ only exists when $\gcd(a, n) = 1$.

Theorems & Applications

Two celebrated theorems make modular computation easy and powerful:

• Fermat's little theorem: If $p$ is prime and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod p$. This provides inverses via $a^{-1} \equiv a^{p-2}$ and enables fast primality tests.
• The Chinese remainder theorem: A system of congruences with coprime moduli has a unique solution modulo the product of moduli, reassembling a number from remainders.

Applications are everywhere:

• Check digits: ISBN and credit cards append a digit making a weighted sum $\equiv 0 \pmod n$ to catch errors.
• Hash functions: Reduce keys modulo a table size.
• Public-key cryptography (RSA): Rests on modular exponentiation being easy while its inverse (factoring or discrete logarithm) is hard.