Modular Arithmetic

In 1801, a twenty-four-year-old Carl Friedrich Gauss published the Disquisitiones Arithmeticae — the book that founded modern number theory and, alongside his prediction that same year of where the lost dwarf planet Ceres would reappear, made his European reputation. Among its many innovations was a deceptively simple notational move: write a ≡ b (mod n) to mean that a and b leave the same remainder when divided by n. The notation made clock arithmetic — the way the hours wrap around from 12 back to 1 — into a serious algebraic structure with its own laws. The framework Gauss built around this notation underwrites every secure communication on the modern internet.

Two integers a and b are congruent modulo n, written a ≡ b (mod n), if n divides their difference: a − b = kn for some integer k. Equivalently, a and b leave the same remainder when divided by n. Congruence is an equivalence relation: reflexive, symmetric, transitive. The equivalence classes are the residue classes mod n, and there are exactly n of them: {0, 1, 2, …, n−1}. Modular arithmetic is the algebra of these classes. Addition, subtraction, and multiplication all respect congruence: if a ≡ a' and b ≡ b' (mod n), then a + b ≡ a' + b' (mod n) and ab ≡ a'b' (mod n). Division is more subtle: a has a multiplicative inverse mod n iff gcd(a, n) = 1. When n is prime, every nonzero residue has an inverse, and ℤ/n forms a finite field — a structure with all the algebraic properties of the rationals. Fermat's little theorem: for any prime p and any integer a not divisible by p, aᵖ⁻¹ ≡ 1 (mod p). Euler's theorem generalizes: a^φ(n) ≡ 1 (mod n) whenever gcd(a, n) = 1, where φ(n) is the Euler totient function (the count of integers from 1 to n coprime to n). The Chinese Remainder Theorem: a system of congruences with pairwise coprime moduli has a unique solution modulo the product. Quadratic reciprocity — Gauss called it the theorema aureum, the golden theorem, and proved it eight different ways — relates the solvability of x² ≡ p (mod q) to that of x² ≡ q (mod p). The Legendre and Jacobi symbols extend the apparatus.