Clock arithmetic: what happens when numbers wrap around
Nine hours after five o'clock is two o'clock. You have been doing this since you were six.
Ask what time it is nine hours after five o'clock and nobody says fourteen o'clock. They say two. Somewhere in the addition you went past twelve and started again.
That wrapping-around is modular arithmetic, and once it has a name it turns out to be behind a surprising amount of machinery.
The notation
We write 17 mod 12 = 5, meaning the remainder when 17 is divided by 12. The number you wrap at - 12 here - is the modulus.
- Clock times work mod 12 (or mod 24)
- Days of the week work mod 7
- Minutes and seconds work mod 60
- Compass bearings work mod 360
Two numbers that leave the same remainder are called congruent. 17 and 5 are congruent mod 12, written 17 = 5 (mod 12). In clock terms they are the same position on the dial, reached by different routes.
Why it makes hard questions easy
What day of the week is it 1,000 days from a Tuesday?
Counting is hopeless. But days repeat every 7, so only the remainder matters: 1000 mod 7 = 6 (since 7 x 142 = 994, leaving 6). Six days after Tuesday is Monday. The other 994 days are complete cycles that change nothing.
7^100 has 85 digits and no calculator will show it to you. Working mod 10 means you only ever track one digit, and the cycle length of 4 does the rest. Reducing a problem to its cycle is the whole technique.
What it is actually used for
Check digits
The last digit of an ISBN, a bank account number or a barcode is usually calculated from the others using modular arithmetic. Type one digit wrong and the sum no longer comes out right mod 10 or mod 11, so the error is caught before anything is sent anywhere.
Hashing
To store items in a table of 1,000 slots, take some number derived from the item and reduce it mod 1000. You get a slot number in range, every time, with one operation. Most fast lookup in software rests on this.
Cryptography
RSA encryption is modular exponentiation with an enormous modulus. It works because you can raise a number to a power mod n quickly, while undoing it without the secret factors is - as far as anyone knows - infeasible. The primes article covers why that gap exists.
Random numbers
Many pseudo-random generators are of the form 'multiply by a constant, add another, take mod m'. Choose the constants badly and the sequence cycles quickly, which is how some early software ended up with visibly repeating 'random' behaviour.
The rules
Addition, subtraction and multiplication all behave normally - you can reduce at any point and get the same answer.
- (a + b) mod n = ((a mod n) + (b mod n)) mod n
- (a x b) mod n = ((a mod n) x (b mod n)) mod n
That is what keeps the numbers small: to compute 123456 x 789012 mod 10, reduce first to 6 x 2 = 12, then mod 10 gives 2. You never handle the large product at all.
Division is the exception and it does not work the obvious way. There is a version of it - the modular inverse - but it only exists when the number shares no factors with the modulus. This is where modular arithmetic stops being a convenience and starts being a subject of its own.
Back to puzzles
Any rule in a reasoning puzzle that cycles is modular arithmetic in disguise. A shape sequence of circle, triangle, square repeating is mod 3. A pattern that shades every fourth cell is mod 4. When you find yourself asking 'where in the cycle does the missing cell fall', you are computing a remainder.