Modular arithmetic is arithmetic on a circle. Two numbers are congruent modulo n if they differ by a multiple of n. A clock does arithmetic mod 12: 10 hours after 5 o'clock is 3, not 15. This simple idea underlies all modern cryptography, hash functions, error-correcting codes, and much of number theory.
Every row and column contains {0,1,2,3,4} exactly once. The five elements form a closed group under addition mod 5. Red: sums that wrap around (≥5).
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
Modular arithmetic defines congruence: a is congruent to b mod n if n divides a-b. Gauss systematised it in 1801. It underlies all modern public-key cryptography: RSA encryption relies on Fermat's Little Theorem, which states that a^(p-1) is congruent to 1 mod p for any prime p not dividing a. Hash functions use modular operations to map large inputs to fixed-size outputs. The integers mod n form a complete ring, and when n is prime, a finite field.