Modular Arithmetic: Clock Math and Remainders

On a 12-hour clock, 9 + 5 = 2.

Not 14. Two. After 9 o'clock, five hours pass, and you're at 2 o'clock. The numbers wrap around.

Modular arithmetic is arithmetic that wraps.

That's the unlock. Instead of letting numbers grow forever, you pick a modulus n and "reset to zero" whenever you hit n. In mod 12: 11 + 1 = 0, 14 = 2, 25 = 1. The entire infinite number line collapses onto a finite circle of remainders.

This isn't just a curiosity. Modular arithmetic is the foundation of modern cryptography, computer science, and algebraic number theory.

The Notation

a ≡ b (mod n)

"a is congruent to b modulo n"

This means: a and b have the same remainder when divided by n.

Equivalently: n divides (a - b).

17 ≡ 5 (mod 12) because 17 - 5 = 12, divisible by 12. 23 ≡ 2 (mod 7) because 23 = 3×7 + 2.

Remainders Define the System

Every integer is congruent to exactly one of {0, 1, 2, ..., n-1} mod n.

These are the residues or remainder classes.

Mod 5: every integer is ≡ 0, 1, 2, 3, or 4.

• 7 ≡ 2 (mod 5)
• 100 ≡ 0 (mod 5)
• -3 ≡ 2 (mod 5) — yes, -3 = -1×5 + 2

Arithmetic Works

You can add, subtract, and multiply in modular arithmetic:

If a ≡ a' (mod n) and b ≡ b' (mod n), then:

• a + b ≡ a' + b' (mod n)
• a - b ≡ a' - b' (mod n)
• a × b ≡ a' × b' (mod n)

Example (mod 7): (15 + 20) mod 7 = 35 mod 7 = 0 Or: 15 ≡ 1, 20 ≡ 6, so 1 + 6 = 7 ≡ 0 ✓

(15 × 20) mod 7 = 300 mod 7 = 6 Or: 1 × 6 = 6 ✓

You can reduce before computing. This keeps numbers small.

Powers in Modular Arithmetic

2¹⁰ mod 7 = ?

Compute step by step, reducing at each step: 2¹ = 2 2² = 4 2³ = 8 ≡ 1 (mod 7) 2⁴ = 2³ × 2 ≡ 1 × 2 = 2 2⁵ ≡ 4 2⁶ ≡ 1 ...

The pattern cycles with period 3: 2, 4, 1, 2, 4, 1, ...

2¹⁰ = 2^(3×3 + 1) ≡ 2¹ = 2 (mod 7)

The Mod 10 System: Last Digits

Arithmetic mod 10 is arithmetic of last digits.

7 × 8 = 56 → last digit 6. That's 56 mod 10.

What's the last digit of 7¹⁰⁰? 7¹ = 7 7² = 49 → 9 7³ = 343 → 3 7⁴ = 2401 → 1 7⁵ → 7, and it cycles.

Period 4. 100 = 4 × 25, so 7¹⁰⁰ ≡ 7⁴ ≡ 1 (mod 10).

Last digit of 7¹⁰⁰ is 1.

Division in Modular Arithmetic

Division doesn't always work. But when it does, it's multiplication by an inverse.

a has an inverse mod n if there exists b with ab ≡ 1 (mod n).

3 × 5 = 15 ≡ 1 (mod 7), so 5 is the inverse of 3 mod 7.

To "divide by 3" mod 7, multiply by 5.

Existence: a has an inverse mod n iff gcd(a, n) = 1.

Finding Inverses

Use the extended Euclidean algorithm.

To find 3⁻¹ mod 11:

Find x such that 3x ≡ 1 (mod 11).

Extended Euclid gives: 3(4) + 11(-1) = 1.

So 3 × 4 = 12 ≡ 1 (mod 11).

3⁻¹ ≡ 4 (mod 11).

Solving Linear Congruences

Solve 5x ≡ 3 (mod 7).

Find 5⁻¹ mod 7: 5 × 3 = 15 ≡ 1 (mod 7), so 5⁻¹ ≡ 3.

x ≡ 3 × 3 = 9 ≡ 2 (mod 7).

Check: 5 × 2 = 10 ≡ 3 (mod 7) ✓

ℤ/nℤ: The Integers Mod n

Formally, the integers mod n form a structure called ℤ/nℤ (or ℤₙ).

Elements: {0, 1, 2, ..., n-1} Operations: +, -, × (mod n)

This is a ring. If n is prime, it's a field (division always works for nonzero elements).

ℤ/7ℤ: Every nonzero element has an inverse. ℤ/6ℤ: 2 and 3 have no inverses (since gcd(2,6) = 2 ≠ 1).

Applications

Hashing: Hash functions often use mod to map large values to table indices.

Checksums: ISBN, credit cards use mod 10 or mod 11 check digits.

Cryptography: RSA uses modular exponentiation with huge moduli.

Computer arithmetic: Fixed-width integers wrap around (that's mod 2³² or mod 2⁶⁴).

Calendars: Days of the week are mod 7.

The Chinese Remainder Theorem

If gcd(m, n) = 1, then for any a, b, there's a unique x (mod mn) satisfying:

x ≡ a (mod m) x ≡ b (mod n)

This lets you break a problem mod mn into smaller problems mod m and mod n.

Example: Find x with x ≡ 2 (mod 3) and x ≡ 3 (mod 5).

By inspection or algorithm: x = 8 works. And 8 is unique mod 15.

The Core Insight

Modular arithmetic creates finite number systems from infinite ones.

Instead of the infinite number line, you work on a circle of n points. Numbers wrap around. This finite system has rich structure — it's where number theory meets algebra.

Clocks, calendars, checksums, cryptography — all run on modular arithmetic.

Part 7 of the Number Theory series.

Previous: Least Common Multiple: When Cycles Align Next: Congruences: When Different Numbers Are the Same