Clock arithmetic: remainders and modular arithmetic

Builds on

Required prerequisites, all the way down: 4

You will learn to

• Compute sums and products modulo n using remainders, for example on a 12-hour clock or in a 7-day week.
• Build addition and multiplication tables modulo n and look for patterns, such as which remainders have a multiplicative partner.
• Explain why the remainder of a sum or product depends only on the remainders of its parts.

Definition

• a mod n is the remainder r, with 0 ≤ r < n, when a is divided by n.
• Addition modulo n: add as usual and take the remainder on division by n; multiplication modulo n works the same way.

Theorem

• (a + b) mod n = ((a mod n) + (b mod n)) mod n, and similarly for multiplication.
• A remainder a has a partner b with ab mod n = 1 exactly when a and n have no common factor greater than 1 (proved later with Euclid's algorithm).
• Modulo a prime p, every non-zero remainder has such a partner.

Common misconceptions

• Thinking modular arithmetic is only about 12-hour clocks.
• Believing that if ab mod n = 0 then a or b must be 0 mod n; in fact 3 × 4 mod 12 = 0.
• Forgetting that a remainder must lie between 0 and n − 1.

Leads to

Optional discoveries

• Congruences Clock arithmetic becomes the theory of congruences: a ≡ b (mod n) when n divides a − b, an equivalence relation that respects + and ×.Wonder Trail →
• Groups The hours of a 12-hour clock under addition form a cyclic group of order 12.Wonder Trail →
• Cryptography Fast modular exponentiation is the engine of RSA and Diffie–Hellman key exchange.
• ← Patterns
• ← Secret codes
• ← Integers