Modular Arithmetic — The Arithmetic of Remainders
You already know modular arithmetic. You just don't know you know it.
Think about a clock. When it's 10 AM and you add 5 hours, you get 3 PM — not 15 o'clock. The clock "wraps around" after 12. That wrapping is the entire idea of modular arithmetic. We care only about the remainder after division, not the full number.
The Intuition: "What's left over?"
Take any two whole numbers and divide one by the other. The result is a quotient (how many times it fits) and a remainder (what's left). Modular arithmetic is the study of that remainder.
For example: 17 divided by 5 gives quotient 3 and remainder 2. In modular language, we say:
17≡2(mod5)
Read this as: "17 is congruent to 2 modulo 5." It means 17 and 2 leave the same remainder when divided by 5.
The word "modulo" comes from Latin — meaning "with respect to the modulus." The modulus is the number you divide by (here, 5).
The Precise Definition
Let a, b, and m be integers, with m>0. We say:
a≡b(modm)
if and only if m divides (a−b) exactly — that is, a−b=m⋅k for some integer k.
Equivalently: a and b have the same remainder when divided by m.
a≡b(modm)⟺m∣(a−b)
Examples to Lock It In
| Statement | Why it's true |
|---|
| 23≡3(mod5) | 23−3=20, and 5 divides 20 |
| 14≡2(mod12) | 14−2=12, and 12 divides 12 |
| 100≡1(mod3) | 100−1=99, and 3 divides 99 |
| 7≡0(mod7) | 7−0=7, and 7 divides 7 |
Notice the last one: any number is congruent to 0 modulo itself. That's just saying the remainder when you divide a number by itself is 0.
What Modular Arithmetic Doesn't Care About
Two numbers that are congruent modulo m are considered "the same" for all modular purposes. So:
...,−10,−5,0,5,10,15,...
are all the same modulo 5. They form an equivalence class — a set of numbers that all share the same remainder.
A common mistake: thinking a≡b(modm) means a divided by m gives remainder b. That's only true if 0≤b<m. The definition is about the difference being divisible by m, not about the remainder itself.
Why It Matters …