modular arithmetic

A clock is the everyday model. Add 5 hours to 10 o'clock and you do not get 15 — you get 3, because the hours wrap around after 12. Modular arithmetic is exactly this kind of counting, where numbers loop back to the start once they reach a fixed value called the modulus.

Working modulo n means we only care about remainders after dividing by n. Two numbers that leave the same remainder are treated as equal, written a ≡ b (mod n). You can add, subtract, and multiply these remainders and the answers stay consistent: (a + b) mod n and (a times b) mod n depend only on the remainders of a and b, not their full size. This lets you replace huge numbers by small ones before computing.

One operation is delicate: division. You cannot always divide modulo n, because not every nonzero remainder has a multiplicative inverse. An inverse for a exists modulo n exactly when a and n are relatively prime. So modulo 12 you can divide by 5 (since gcd(5,12)=1) but not by 6. This is why prime moduli are so pleasant — every nonzero remainder is then invertible.