Modular Arithmetic
Modular arithmetic forms the backbone of computer science, cryptography, and digital clocks, yet students often struggle with its abstract nature. When teaching this concept, start with concrete examples like clock arithmetic—asking students what time it will be 25 hours from now when it's currently 3 PM helps them grasp the cyclical nature of remainders.
Try it right now
Click “Generate a problem” to see a fresh example of this technique.
Why it matters
Modular arithmetic powers the digital world around us. Credit card numbers use modular arithmetic for validation—the 16th digit is calculated using mod 10 operations on the first 15 digits. Computer hash functions rely on modular operations to distribute data evenly across memory locations. In cryptography, RSA encryption uses modular exponentiation with numbers containing hundreds of digits. Students encounter modular arithmetic daily: a 12-hour clock uses mod 12 (3 + 25 hours = 4 PM the next day), while computer memory addresses cycle using powers of 2. Even simple applications like determining if a year is divisible by 4 for leap years involves modular thinking. Understanding these patterns helps students recognize mathematical structures in technology, finance, and scheduling systems they use constantly.
How to solve modular arithmetic
Modular Arithmetic (Congruences)
- a mod n is the remainder when a is divided by n: a = n·q + r with 0 ≤ r < n.
- a ≡ b (mod n) means (a − b) is a multiple of n — equivalently, a and b leave the same remainder when divided by n.
- Addition and multiplication respect congruence: (a + b) mod n and (a · b) mod n can be computed by reducing each part mod n first.
- To solve ax ≡ b (mod n) when gcd(a, n) = 1, multiply both sides by the modular inverse of a.
Example: 17 mod 5 = 2 (since 17 = 3·5 + 2). And 17 ≡ 2 (mod 5) because 17 − 2 = 15 is a multiple of 5.
Worked examples
Compute 19 mod 7.
Answer: 5
- Find the largest multiple of 7 that is ≤ 19 → 7 × 2 = 14 — We want the biggest number of the form 7·k that does not exceed 19. Dividing, 19 ÷ 7 = 2 with something left over, so 7·2 = 14.
- Subtract to find the remainder → 19 − 14 = 5 — The remainder is what is left after removing the multiple: 19 − 14 = 5.
- State the answer → 19 mod 7 = 5 — So 19 mod 7 = 5 (since 19 = 7·2 + 5).
Is 52 ≡ 46 (mod 11)?
Answer: no
- Compute the difference a − b → 52 − 46 = 6 — Two numbers are congruent mod n exactly when their difference is a multiple of n. So we compute 52 − 46 = 6.
- Check whether 6 is divisible by 11 → 6 = 11 · 0 + 6 — Dividing: 6 ÷ 11 = 0 remainder 6. The remainder is 6 ≠ 0, so the difference is not a multiple of n.
- Answer → No — 52 ≢ 46 (mod 11) — No: since 6 is not a multiple of 11, we have 52 ≢ 46 (mod 11).
Compute (13 × 9) mod 10.
Answer: 7
- Compute the product first → 13 × 9 = 117 — Do the arithmetic inside first: 13 × 9 = 117.
- Reduce 117 modulo 10 → 117 = 10 · 11 + 7 — Divide 117 by 10: 117 ÷ 10 = 11 remainder 7. The remainder is what we keep.
- State the answer → (13 × 9) mod 10 = 7 — So (13 × 9) mod 10 = 117 mod 10 = 7.
Common mistakes
- Students often confuse 17 mod 5 with 17 ÷ 5, writing 3.4 instead of the correct remainder 2.
- When checking congruence, students incorrectly verify 28 ≡ 13 (mod 7) by computing 28 mod 7 = 0 and 13 mod 7 = 6, concluding they're not congruent, when both actually equal 0 and 6 respectively, making them incongruent.
- For modular multiplication like (15 × 8) mod 7, students often reduce each factor first: (1 × 1) mod 7 = 1, instead of computing 120 mod 7 = 1.
- Students frequently forget that negative remainders need adjustment—computing (-23) mod 5 as -3 instead of the correct positive remainder 2.