Modular Arithmetic
“Modular arithmetic is clock arithmetic—go all the way around and you're back at the start.”
The formula
a ≡ b (mod n) ⟺ n | (a − b)How to read it: a and b are congruent mod n when they leave the same remainder on division by n—that is, n divides a−b
- a ≡ b
- — the sign that a and b are congruent (same remainder)
- mod n
- — means measuring with respect to modulus n—12 for a clock
- n | (a−b)
- — n divides a−b (their difference is a multiple of n)
The hook
On a clock, five hours after 9 is not 14 but 2. This 'wrap around to the start' arithmetic is modular arithmetic.
In plain words
Modular arithmetic is arithmetic that wraps back to 0 after some number n. Two numbers are 'congruent' if they leave the same remainder when divided by n, written a ≡ b (mod n). Only the remainder matters.
The intuition
Instead of laying the number line out straight, imagine wrapping it around a circle (a clock face) with n slots. Cross n and you return to 0. On a 12-hour clock 17:00 lands on 5—so 17 and 5 are congruent mod 12. Big numbers get folded down to a 'position on the wheel'.
How it's built
The key is the remainder. The remainder of a divided by n is a's 'value mod n'. Addition, subtraction, and multiplication all carry through on the remainders, so you never need the big numbers—just juggle the remainders: (a+b) mod n is the sum of the remainders, reduced mod n.
Example
Why 17 ≡ 5 (mod 12): 17 − 5 = 12 is a multiple of 12. On a clock, 17:00 is 5 PM. Also 25 mod 7 = 4, because 25 = 3·7 + 4.
Common mistake
By common convention the remainder is never negative. For example −1 mod 5 is not −1 but 4 (since −1 = (−1)·5 + 4). It's like stepping one hour back on a clock to land on 11.
Where it's used
The heart of modern cryptography (RSA, elliptic curves), hash functions and checksums (ISBN and credit-card validation), day-of-week and calendar computations, random number generators, the 12-tone musical scale—modular arithmetic runs every cyclic computation.
Where it came from
Gauss introduced the congruence sign ≡ in his 1801 Disquisitiones Arithmeticae, systematizing number theory. It was a signature tool of the man who called number theory 'the queen of mathematics'.
Prerequisites
Quick check
What is 25 mod 7? (the remainder of 25 divided by 7)
- 3
- 4✓
- 5
- 11
Practice
Compute 17 mod 5.
Answer: 2
- 17 = 3·5 + 2
- the remainder is 2
Takeaway: a mod n is the remainder after dividing by n.
Compute (7 + 8) mod 12.
Answer: 3
- 7 + 8 = 15
- 15 mod 12 = 3 (once around, then 3)
Takeaway: Clock arithmetic—pass 12 and start again from 0.
Compute (4 × 6) mod 5.
Answer: 4
- 4 × 6 = 24
- 24 = 4·5 + 4, remainder 4
Takeaway: Multiplication carries through on remainders too.
If today is Monday, what day is it 100 days later? (use mod 7)
Answer: 1
- 100 mod 7 = 2 (since 98 = 14·7, remainder 2)
- Monday + 2 days = Wednesday
Takeaway: Day-of-week is mod 7—every 7 days returns to the start.