A Practical Introduction to Modular Arithmetic

What Modular Arithmetic Actually Is

Think of a 12-hour clock. If it is 10 o'clock and you add 4 hours, you get 2 o'clock, not 14. That is modular arithmetic: you wrap around after reaching the modulus. The remainder when dividing by 12. So 14 mod 12 = 2, and 17 mod 5 = 2 because 5 goes into 17 three times with 2 left over.

We say two numbers are congruent modulo n if their difference is a multiple of n. Write a ≡ b (mod n). For example: 17 ≡ 2 (mod 5), 100 ≡ 4 (mod 12), and -1 ≡ 25 (mod 26). That last one is handy for ciphers: negative shifts wrap around to the end of the alphabet.

The Rules of the Wrap-Around

You can add, subtract, and multiply as usual, as long as you reduce modulo n at the end. (a + b) mod n = ((a mod n) + (b mod n)) mod n. Same for multiplication. Example: (17 + 15) mod 12 = 32 mod 12 = 8. And (5 × 8) mod 7 = 40 mod 7 = 5.

Division is different. You cannot always divide. For example, 2 × x ≡ 4 (mod 6) has two solutions: x = 2 and x = 5. So we need modular inverses. An inverse of a modulo n is a number b such that a × b ≡ 1 (mod n). It exists only if a and n are coprime (no common factors other than 1). Example: 3 × 5 = 15 ≡ 1 (mod 7), so 5 is the inverse of 3 modulo 7.

Cracking a Caesar Cipher with Modular Arithmetic

The Caesar cipher shifts each letter by a fixed number. Map A=0, B=1, ..., Z=25. Encryption: C = (P + k) mod 26. Decryption: P = (C - k) mod 26, adding 26 if the result is negative.

Try it with shift k=3. Plain "HELLO": H=7, E=4, L=11, L=11, O=14. Cipher: (7+3)=10 → K, (4+3)=7 → H, (11+3)=14 → O, (11+3)=14 → O, (14+3)=17 → R. So "KHOOR". To decrypt "WKLV" with k=3: W=22 → 22-3=19 → T, K=10 → 7 → H, L=11 → 8 → I, V=21 → 18 → S. "THIS". Only 26 possible shifts, so you can brute-force, but modular arithmetic makes it precise.

Modular Inverses and Affine Ciphers

The affine cipher uses E(x) = (a×x + b) mod 26. To decrypt, you need the inverse of a modulo 26. Since 26 = 2 × 13, a must be coprime with 26: it cannot be even or a multiple of 13. Valid a values: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25.

Example: a=5, b=8. E(x) = (5x + 8) mod 26. Encrypt "CAT": C=2 → (10+8)=18 → S. A=0 → 8 → I. T=19 → (95+8)=103 mod 26. 26×3=78, 103-78=25 → Z. So "SIZ". To decrypt, find inverse of 5 mod 26: 5×21=105, 105 mod 26 = 1 (since 26×4=104). So inverse is 21. D(y) = 21×(y - 8) mod 26. Check S=18: 21×10=210 mod 26. 26×8=208, remainder 2 → C. Works.

Puzzles, Checksums, and Digital Security

Modular arithmetic is behind many everyday puzzles. ISBN-10 check digit: multiply the first 9 digits by 10 down to 2, add them, then add the check digit, and the total must be divisible by 11. Example: 0123456789. Sum = (10×0)+(9×3)+(8×0)+(7×6)+(6×4)+(5×0)+(4×6)+(3×1)+(2×5) = 0+27+0+42+24+0+24+3+10 = 130. Add check digit 2: 132. 132 mod 11 = 0. Valid.

Day-of-week puzzle: If today is Wednesday, what day is it in 100 days? 100 mod 7 = 2. Wednesday + 2 = Friday.

Every time you see a padlock in your browser, modular arithmetic is working. Diffie-Hellman key exchange: two people agree on a large prime p and base g. Alice picks secret a, sends g^a mod p. Bob picks secret b, sends g^b mod p. Both compute the same shared secret g^(ab) mod p. An eavesdropper sees p, g, g^a, and g^b, but finding a from g^a mod p is the discrete logarithm problem, believed to be very hard for large numbers. RSA works similarly: public key (n, e) where n = p×q, encryption C = M^e mod n, decryption M = C^d mod n where e×d ≡ 1 mod (p-1)(q-1). Without p and q, finding d is difficult. That is the magic of modular arithmetic: a one-way street that is easy to go down but hard to climb back up.