Modular Arithmetic

Modular arithmetic is simply arithmetic where you only keep the remainder, so numbers wrap around like the hours on a clock. "Mod" is short for modulo, Latin for "by the measure of": you measure a number by $n$ and keep what's left over. You already use it to tell time and to work out days of the week, and every modern cipher runs on it. The statement $a \equiv b \pmod{n}$ looks formal, but it's just "$a$ and $b$ land on the same spot on an $n$-hour clock," and $n \mid (a - b)$ (n goes evenly into the gap between them) is the same idea said with division. Nothing more to it than that.

$17 \equiv 5 \pmod{12}$: 17 o'clock is 5 o'clock. Every integer is congruent to exactly one of $0, 1, \dots, n - 1$ mod $n$, its remainder from the division you saw two lessons ago.

Rules. If $a \equiv b$ and $c \equiv d \pmod n$, then $a + c \equiv b + d$ and $ac \equiv bd \pmod n$. Why should that be true? Write $a = b + jn$ and $c = d + kn$. Then $ac = bd + (bk + dj + jkn)n$, and everything past $bd$ is a multiple of $n$, so it vanishes mod $n$. Addition works the same way. That's what makes this so handy: you can reduce at every step and keep the numbers small. Division is the exception; it needs inverses, which are the next lesson.

Big powers. To find $3^{20} \bmod 7$, notice $3^6 \equiv 1 \pmod 7$, so $3^{20} = (3^6)^3 \cdot 3^2 \equiv 9 \equiv 2$. Once some power is 1, the powers repeat in a cycle, and you only need the exponent's remainder. In general, repeated squaring computes $a^k \bmod n$ with about $\log_2 k$ multiplications.

Divisibility tests are modular facts in disguise. Since $10 \equiv 1 \pmod 9$, every power of 10 is also $\equiv 1$, so a number is congruent to its digit sum mod 9, and it's divisible by 9 exactly when its digit sum is.

Calendars. Days of the week are arithmetic mod 7. 100 days from Monday: $100 \equiv 2 \pmod 7$, so it's a Wednesday.

Clocks, calendars, hash tables, check digits on barcodes and every modern cipher run on modular arithmetic.