MISSION · Number sense
Modular Arithmetic
Clock arithmetic, and what it secures
LEVEL 1 · EXPLORE
Make the idea move
Change the controls and watch what happens. Follow your curiosity and see what you notice.
Loading the activity…
LEVEL 2 · LEARN
Unlock the explanation
Open the chapters in any order. Try the examples as you go.
The idea in one sentence
Fix a modulus, keep only the remainder after dividing by it, and you get a small closed number system where arithmetic still works.
The clock
It’s 10 o’clock. What time is it in 5 hours? Three — not fifteen. The clock wraps at 12, so you work with remainders:
\[10 + 5 = 15 \equiv 3 \pmod{12}\]That \(\equiv\) is read “is congruent to”. Two numbers are congruent mod \(n\) when they leave the same remainder — which is the same as saying their difference is a multiple of \(n\).
Working mod 12 leaves exactly twelve numbers, 0 to 11, and every integer collapses into one of them. Mod 2 leaves two: the evens and the odds. You have been doing modular arithmetic since you first noticed that odd plus odd is even.
Arithmetic survives the collapse
Addition, subtraction, and multiplication all work the way you’d want: reduce first or reduce last, the answer agrees.
\[17 \times 23 \pmod 5\]Either multiply to 391 and take the remainder, 1. Or reduce first — \(17 \equiv 2\) and \(23 \equiv 3\) — then \(2 \times 3 = 6 \equiv 1\). Same answer, far less arithmetic.
That shortcut makes otherwise impossible calculations easy. The last digit of \(7^{100}\) means \(7^{100} \bmod 10\), and powers of 7 cycle 7, 9, 3, 1 with period 4. Since 100 is a multiple of 4, the answer is 1.
Division is the exception. You can’t simply divide, and \(\frac{1}{2}\) has no meaning here. Sometimes an inverse exists — mod 7, doubling 4 gives 1, so 4 acts as “a half” — and sometimes nothing works at all. Division is the operation modular arithmetic doesn’t inherit for free, and that turns out to be exactly the property cryptography exploits.
Where it earns its keep
Check digits. The last digit of an ISBN or a bank account number is chosen so a weighted sum comes to 0 mod 10 or 11. Mistype one digit and the sum fails — the error is caught before anything is processed.
Cryptography. RSA encryption rests on modular exponentiation being quick to do and brutally slow to undo without the key. The entire security of online payment sits on the asymmetry of arithmetic mod a very large number.
Hashing and scheduling. Any time a system has to fit unbounded values into a fixed
number of slots — hash tables, round-robin rotas, days of the week — it’s % doing the
work.
Calendars. What day is it in 1000 days? \(1000 \bmod 7 = 6\), so six days on. Nobody counts.
Common mix-ups
- Negative remainders. \(-3 \bmod 7\) is 4, not \(-3\). Add the modulus until you land in range. Many programming languages disagree with mathematics here, and it causes real bugs.
- Dividing. Not generally allowed.
- Mixing moduli in one calculation.
- Confusing congruence with equality. \(17 \equiv 5 \pmod{12}\) does not make them the same number.
Check yourself
What is \((23 + 19) \bmod 7\), and what is \(-5 \bmod 12\)?
\(23 \equiv 2\) and \(19 \equiv 5\), so the sum is \(7 \equiv 0 \pmod 7\). And \(-5 + 12 = 7\), so \(-5 \equiv 7 \pmod{12}\).
LEVEL 3 · REFLECT
Add this quest to your trail
When you feel ready, mark this idea as explored. You can always come back and try it again.
EXPLORER STRATEGIES