Modular Arithmetic and Congruence

Reading a clock is modular arithmetic

On a 12-hour clock, 5 hours after 9 o'clock is 2 o'clock, not 14. We quietly wrapped around: 14 and 2 leave the same remainder when divided by 12. [[modular-arithmetic|Modular arithmetic]] makes this official. We say a is [[congruence-modulo-n|congruent]] to b modulo n, written a ≡ b (mod n), when a and b have the same remainder on division by n — equivalently, when n divides a − b.

17 ≡ 5 (mod 12)   because 17 − 5 = 12, and 12 | 12
38 ≡ 2 (mod 12)   because 38 = 12·3 + 2
-1 ≡ 11 (mod 12)  because -1 = 12·(-1) + 11

Every integer is congruent to exactly one of
0, 1, 2, …, 11 modulo 12 — its remainder.

Modulo 12, every integer collapses to one of the twelve remainders 0–11.

Arithmetic survives the wrap-around

The magic is that congruence respects addition and multiplication. If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d (mod n) and a·c ≡ b·d (mod n). So you may reduce numbers to their remainders at any time during a calculation — which keeps the numbers small.

Find the last digit of 7^4 — i.e. 7^4 (mod 10).

  7^2 = 49 ≡ 9 (mod 10)
  7^4 = (7^2)^2 ≡ 9^2 = 81 ≡ 1 (mod 10)

So 7^4 ends in 1.  (Indeed 7^4 = 2401.) ✓

We never computed 2401 — we stayed under 100.

Reducing mod 10 at each step finds the last digit without ever computing the full power.

Where this shows up

Modular arithmetic is everywhere once you look: days of the week (mod 7), the check digit on an ISBN, the hands of every clock, and the public-key cryptography that protects online banking. The same idea, applied to remainders, also lets us decide when the [[diophantine-equation|Diophantine equations]] of the final guide have whole-number solutions.