Modular Arithmetic – Clock Math and Remainders
Modular arithmetic is a system of arithmetic where numbers “wrap around” after reaching a fixed value, called the modulus. Written a mod n, it simply means the remainder when a is divided by n. It is often nicknamed clock arithmetic, because a 12-hour clock is the everyday example everyone already knows: the hour hand wraps back to 1 after passing 12, no matter how many hours have actually gone by.
The formal notation and systematic theory of modular arithmetic were introduced by Carl Friedrich Gauss in his 1801 book Disquisitiones Arithmeticae, where he invented the congruence symbol “≡” still used today. The underlying idea, though, is far older: the Chinese text Sunzi Suanjing (Sun Zi's Mathematical Classic, dated to somewhere between the 3rd and 5th centuries CE) already posed and solved remainder puzzles – asking for a number that leaves specific remainders when divided by several different values – more than a thousand years before Gauss gave the subject its modern name and notation.
What Is Modular Arithmetic?
For a whole number a and modulus n, a mod n is the remainder left over when a is divided by n. The result always lies between 0 and n−1. For example, 17 mod 5 = 2, because 17 = 3×5 + 2.
The Rules of Modular Arithmetic
| Operation | Rule |
|---|---|
| Addition | (a + b) mod n = ((a mod n) + (b mod n)) mod n |
| Subtraction | (a − b) mod n = ((a mod n) − (b mod n)) mod n |
| Multiplication | (a × b) mod n = ((a mod n) × (b mod n)) mod n |
23 + 15 = 38.
38 ÷ 7 = 5 remainder 3, so 38 mod 7 = 3.
Clock Arithmetic
A standard 12-hour clock is modular arithmetic with modulus 12 (except that it labels the remainder 0 as “12” instead). Days of the week work the same way with modulus 7.
9 + 20 = 29.
Using ((29 − 1) mod 12) + 1 = (28 mod 12) + 1 = 4 + 1 = 5 o’clock.
Real-World Applications
- Check digits: ISBN book codes and the Luhn algorithm used to validate credit card numbers are both built from modular arithmetic.
- Computer science: Hash tables use a mod n to decide which “bucket” to store data in, and circular buffers use it to wrap array indices.
- Calendars: Working out the day of the week for any date (Zeller's congruence) is a modular arithmetic calculation.
- Cryptography: RSA encryption, covered later in this section, performs almost all of its calculations modulo a large number n.
Key Takeaways
- a mod n is the remainder when a is divided by n, always between 0 and n−1.
- Addition, subtraction, and multiplication can each be done “mod n” at every step, keeping numbers small.
- A 12-hour clock and the days of the week are modular arithmetic in everyday life.
- Modular arithmetic underlies check digits, hashing, calendars, and modern cryptography.