Concept
The arithmetic of clocks — wrapping around at a modulus. The basic language of number theory and cryptography.
Understand it in one breath
Integers belong to the same class when they leave the same remainder modulo n. This appears naturally in clocks, calendars, checksums, and number theory; Gauss systematized congruence notation and theory in 1801. RSA and Diffie–Hellman use modular arithmetic centrally, while hashes, error correction, and internet security also require other algebra and protocols.
At a glance
× | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
2 | 0 | 2 | 4 | 6 | 1 | 3 | 5 |
3 | 0 | 3 | 6 | 2 | 5 | 1 | 4 |
4 | 0 | 4 | 1 | 5 | 2 | 6 | 3 |
5 | 0 | 5 | 3 | 1 | 6 | 4 | 2 |
6 | 0 | 6 | 5 | 4 | 3 | 2 | 1 |
Multiplication table mod 7 — every nonzero row contains exactly one 1, a consequence of 7 being prime.
Key formula
Worked examples
- 1
Q.7 o’clock + 8 hours = ?
- 2
Q.3 × 5 (mod 7)
Key moments
Euclid’s Elements — a precursor to congruence
Euclid already used the greatest-common-divisor algorithm. The tools of modular arithmetic existed long before its formal notation.
Gauss — Disquisitiones Arithmeticae
At age 24, Gauss introduced congruence notation (≡) and organized modular arithmetic into a general theory, transforming number theory.
Fermat’s little theorem
The congruence a^p ≡ a (mod p) for prime p became a core tool of public-key cryptography more than three centuries later.
RSA — modular arithmetic secures the network
Ron Rivest, Adi Shamir, and Leonard Adleman built public-key encryption from modular exponentiation and the difficulty of factoring a product of large primes.
Modern applications
RSA, Diffie–Hellman, and elliptic-curve cryptography; hash functions; checksums; and twelve-tone music theory.
Beyond MathVoyage
Loading…