In 1801, a twenty-four-year-old Carl Friedrich Gauss — already widely recognized as the foremost mathematician in Europe — published the Disquisitiones Arithmeticae. The book founded modern number theory. 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.
Modular arithmetic is the foundation of all of public-key cryptography. RSA relies on the difficulty of factoring large composites n = pq and the easy computation of modular exponentiation. Diffie-Hellman key exchange uses discrete logarithms in (ℤ/p)\*. Elliptic-curve cryptography — the workhorse of modern TLS, Bitcoin, and Signal — uses point arithmetic on elliptic curves over finite fields. Hash functions in computer science distribute inputs across hash tables using modular arithmetic. Error-correcting codes (Reed-Solomon for QR codes and CDs, BCH for satellite communication) are constructed over finite fields via modular arithmetic. Pseudorandom number generators — including the Mersenne Twister used in most simulation work — rely on modular operations. The little equivalence relation Gauss formalized in 1801 secures every HTTPS connection in the modern world.