Modular Arithmetic
Modular arithmetic forms the backbone of digital security systems and computer programming, yet many Year 10 students struggle with the concept of remainders in mathematical contexts. Understanding how numbers 'wrap around' after reaching a certain value proves essential for GCSE Further Mathematics and A-level preparation.
Try it right now
Click “Generate a problem” to see a fresh example of this technique.
Why it matters
Modular arithmetic governs everyday digital life through encryption protocols that protect online banking and messaging apps. Computer scientists use modular arithmetic in hash functions, where data gets mapped to fixed-size values—a process behind password storage systems. The 12-hour clock system demonstrates modular arithmetic in action: 9 o'clock plus 5 hours equals 2 o'clock, not 14 o'clock. Credit card validation relies on modular 10 arithmetic through the Luhn algorithm, which catches 70% of single-digit errors. Even music theory employs modular 12 arithmetic for octave relationships. GCSE Computing students encounter modular arithmetic in binary operations and data structures. Understanding these concepts prepares students for university-level discrete mathematics, cryptography, and computer science courses. The skills transfer directly to problem-solving in programming languages where overflow conditions and cyclic patterns appear frequently.
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 45 mod 4.
Answer: 1
- Find the largest multiple of 4 that is ≤ 45 → 4 × 11 = 44 — We want the biggest number of the form 4·k that does not exceed 45. Dividing, 45 ÷ 4 = 11 with something left over, so 4·11 = 44.
- Subtract to find the remainder → 45 − 44 = 1 — The remainder is what is left after removing the multiple: 45 − 44 = 1.
- State the answer → 45 mod 4 = 1 — So 45 mod 4 = 1 (since 45 = 4·11 + 1).
Is 13 ≡ 39 (mod 12)?
Answer: no
- Compute the difference a − b → 13 − 39 = -26 — Two numbers are congruent mod n exactly when their difference is a multiple of n. So we compute 13 − 39 = -26.
- Check whether -26 is divisible by 12 → -26 = 12 · -3 + 10 — Dividing: -26 ÷ 12 = -3 remainder 10. The remainder is 10 ≠ 0, so the difference is not a multiple of n.
- Answer → No — 13 ≢ 39 (mod 12) — No: since -26 is not a multiple of 12, we have 13 ≢ 39 (mod 12).
Compute (22 + 13) mod 7.
Answer: 0
- Compute the sum first → 22 + 13 = 35 — Do the arithmetic inside first: 22 + 13 = 35.
- Reduce 35 modulo 7 → 35 = 7 · 5 + 0 — Divide 35 by 7: 35 ÷ 7 = 5 remainder 0. The remainder is what we keep.
- State the answer → (22 + 13) mod 7 = 0 — So (22 + 13) mod 7 = 35 mod 7 = 0.
Common mistakes
- Students confuse 17 mod 5 with 17 ÷ 5, writing 3.4 instead of the correct remainder 2
- When checking 23 ≡ 8 (mod 5), students subtract incorrectly and claim 15 ≢ 0 (mod 5) instead of recognising 23 - 8 = 15 = 3 × 5
- For (18 + 27) mod 6, students compute 18 mod 6 = 0 and 27 mod 6 = 3, then write 0 + 3 = 3, missing that 45 mod 6 = 3 anyway
- Students think 7x ≡ 4 (mod 9) has solution x = 4 ÷ 7, not recognising they need the modular inverse of 7