Arithmetic Mod n

Look at a clock. It is four o'clock, and you wait four hours — you land on eight. Wait four more, and you reach twelve. Wait four more… and you are back at four, not sixteen. The clock only knows the numbers 1 through 12; when a sum runs off the end, it quietly wraps around to the start again.

That wrapping is the whole idea of modular arithmetic: doing sums in a world where numbers cycle back to zero once they reach some fixed size n. It looks like a children's puzzle, yet it is the secret engine behind calendars, computing, error-detecting barcodes, and the cryptography that guards every message you send online. Turn the dial below and watch a clock do arithmetic.

Remainder, congruence, and the clock world

Strip the idea to its bones. a \bmod n is simply the remainder left when you divide a by n. On a 12-hour clock n = 12; on a week n = 7; inside a byte n = 256. So

17 \bmod 5 = 2, \qquad 23 \bmod 7 = 2, \qquad 100 \bmod 12 = 4.

Two whole numbers are called congruent modulo n, written a \equiv b \pmod n, when they leave the same remainder — equivalently, when n divides their difference. Thus 17 \equiv 2 \pmod 5 and 23 \equiv 2 \equiv 100 \equiv 30 \pmod 7: different-looking numbers that sit on the same spot of the dial. This turns the infinite world of integers into a small, closed system with only n elements: \mathbb{Z}_n = \{0, 1, \dots, n-1\}.

The power of congruence: you can compute with it

If a \equiv a' and b \equiv b' \pmod n, then

The practical upshot: reduce early and often. You never have to carry big numbers — replace anything by its remainder whenever you like. To find 17 \cdot 14 \bmod 5, don't compute 238; reduce first:

17 \cdot 14 \equiv 2 \cdot 4 = 8 \equiv 3 \pmod 5.

Three worked examples

1. A simple sum on the clock. What is (8 + 6) \bmod 12? Add normally to get 14, then subtract a full turn of 12:

(8 + 6) \bmod 12 = 14 \bmod 12 = 2.

Eight o'clock plus six hours is two o'clock — exactly what the dial above shows.

2. A product, reduced at each step. Find (8 \cdot 6) \bmod 12. Here 8 \cdot 6 = 48, and 48 = 4 \cdot 12, so (8 \cdot 6) \bmod 12 = 0. The product landed exactly on a multiple of the modulus, so it wraps back to zero.

3. What day of the week? Today is Wednesday; what day is it 100 days from now? Days of the week repeat every 7, so we only care about 100 \bmod 7. Since 100 = 14 \cdot 7 + 2, we have 100 \equiv 2 \pmod 7: just two days past Wednesday, which is Friday. The other 98 days are whole weeks that leave you where you started.

Taming huge powers

This is how we tame quantities that would otherwise be unimaginable. What is the last digit of 7^{100}? "Last digit" means modulo 10. The powers of 7 cycle:

7^1 \equiv 7,\quad 7^2 \equiv 9,\quad 7^3 \equiv 3,\quad 7^4 \equiv 1 \pmod{10},

then repeat every four. Since 100 = 4 \cdot 25, we land on 7^{100} \equiv (7^4)^{25} \equiv 1^{25} = 1 \pmod{10}. The last digit is 1 — found without ever writing the 85-digit number.

By the usual convention, a \bmod n always lands in the range 0, 1, \dots, n-1 — never negative. So what is -1 \bmod 5? Not -1. Keep adding n = 5 until you land in range: -1 + 5 = 4, so -1 \equiv 4 \pmod 5. (Beware: many programming languages return -1 for -1 \,\%\, 5 — their % keeps the sign of the dividend, which is not the mathematician's mod.)

A second trap: congruence is about equal remainders, not equal numbers. Writing 17 \equiv 2 \pmod 5 does not claim 17 = 2; it says they sit on the same spot of the mod-5 dial. Keep "mod" the operation distinct from ordinary equality.

A warning: division is different

Addition, subtraction and multiplication all transfer cleanly. Division does not. From 2 \cdot 3 \equiv 2 \cdot 0 \pmod 6 you cannot cancel the 2 to get 3 \equiv 0 — that's false. Why cancellation sometimes works and sometimes fails, and how to "divide" properly, is the subject of modular inverses.

Modular arithmetic is everywhere in the digital world. Clocks and calendars wrap with it. The last digit of an ISBN or a barcode is a check-digit computed mod 10 or 11 — swap two digits or mistype one and the sum no longer matches, so the scanner catches the error. Hash tables squeeze keys into buckets with \bmod, and random-number generators churn out digits by repeatedly multiplying mod a big number.

And above all: when you buy something online, RSA and modern cryptography scramble your card number using arithmetic mod a colossal number — encryption is, at heart, clever multiplication and exponentiation on an unimaginably large clock face. The "wrap-around" a child meets on a wall clock is the very same mathematics securing the entire internet.