Im Jahr 1801 legte ein vierundzwanzigjähriger Carl Friedrich Gauß — schon weithin als der bedeutendste Mathematiker Europas anerkannt — die Disquisitiones Arithmeticae vor. Das Buch begründete die moderne Zahlentheorie. Unter seinen vielen Neuerungen stand ein scheinbar harmloser Kniff in der Notation: schreibe a ≡ b (mod n), um auszudrücken, dass a und b beim Teilen durch n denselben Rest hinterlassen. Aus der Uhrenarithmetik — wie die Stunden von 12 wieder auf 1 umspringen — wurde damit eine ernsthafte algebraische Struktur mit eigenen Gesetzen. Der Rahmen, den Gauß um diese Notation legte, trägt heute jede sichere Verbindung des Internets.
Zwei ganze Zahlen a und b heißen kongruent modulo n, geschrieben a ≡ b (mod n), wenn n ihre Differenz teilt: a − b = kn für eine ganze Zahl k. Gleichbedeutend: a und b hinterlassen denselben Rest beim Teilen durch n. Die Kongruenz ist eine Äquivalenzrelation: reflexiv, symmetrisch, transitiv. Die Äquivalenzklassen sind die Restklassen mod n, und davon gibt es genau n: {0, 1, 2, …, n−1}. Die Modulararithmetik ist die Algebra dieser Klassen. Addition, Subtraktion und Multiplikation respektieren die Kongruenz: ist a ≡ a' und b ≡ b' (mod n), so ist a + b ≡ a' + b' (mod n) und ab ≡ a'b' (mod n). Die Division ist heikler: a besitzt ein multiplikatives Inverses mod n genau dann, wenn gcd(a, n) = 1. Ist n eine Primzahl, hat jeder von null verschiedene Rest ein Inverses, und ℤ/n ist ein endlicher Körper — eine Struktur mit allen algebraischen Eigenschaften der rationalen Zahlen. Der kleine Satz von Fermat: für jede Primzahl p und jede ganze Zahl a, die nicht durch p teilbar ist, gilt aᵖ⁻¹ ≡ 1 (mod p). Der Satz von Euler verallgemeinert das: a^φ(n) ≡ 1 (mod n), sofern gcd(a, n) = 1; dabei ist φ(n) die eulersche Totientenfunktion (die Anzahl der ganzen Zahlen von 1 bis n, die zu n teilerfremd sind). Der Chinesische Restsatz: ein System von Kongruenzen mit paarweise teilerfremden Modulen besitzt eine eindeutige Lösung modulo dem Produkt. Das quadratische Reziprozitätsgesetz — Gauß nannte es das theorema aureum, den goldenen Satz, und bewies es auf acht Weisen — verknüpft die Lösbarkeit von x² ≡ p (mod q) mit der von x² ≡ q (mod p). Die Legendre- und Jacobi-Symbole erweitern den Apparat.
Die Modulararithmetik trägt die gesamte Public-Key-Kryptographie. RSA lebt von der Schwierigkeit, große zusammengesetzte Zahlen n = pq zu faktorisieren, und von der leichten Berechnung modularer Potenzen. Der Diffie-Hellman-Schlüsselaustausch nutzt diskrete Logarithmen in (ℤ/p)\*. Die Elliptische-Kurven-Kryptographie — das Zugpferd des heutigen TLS, von Bitcoin und Signal — rechnet mit Punkten auf elliptischen Kurven über endlichen Körpern. Hashfunktionen in der Informatik verteilen Eingaben mittels Modulararithmetik über Hashtabellen. Fehlerkorrigierende Codes (Reed-Solomon für QR-Codes und CDs, BCH für Satellitenkommunikation) werden über endliche Körper konstruiert. Pseudozufallsgeneratoren — darunter der Mersenne-Twister, mit dem ein Großteil der Simulationsarbeit läuft — fußen auf modularen Operationen. Die kleine Äquivalenzrelation, die Gauß 1801 formalisierte, sichert jede HTTPS-Verbindung der modernen Welt.