Arithmetic on a clock

On a clock, 9 o'clock plus 5 hours is 2 o'clock. Nobody finds that strange. Do the same thing with multiplication and powers on a clock whose size is a prime number, and a regular pattern shows up: every non-zero number, raised to the right power, lands back on 1.

What it is

Pick a clock size n. Two whole numbers are congruent mod n, written a ≡ b (mod n), when n divides a − b — that is, when they leave the same remainder after dividing by n. So 14 ≡ 2 (mod 12), and so does 26. Stein's textbook builds arithmetic on these remainder classes: add, subtract or multiply, then keep only the remainder. The numbers never grow; they wrap round the dial.

Why it matters

Wrapping keeps every number small, however large the power, which is why computers can work with it. Clock arithmetic is the machinery under the key exchange and the public-key cipher explained elsewhere on this site. This page is about the one pattern those schemes lean on, and about a tempting shortcut built from it that does not work.

The pattern

Not every number behaves well on every clock. On a 12-hour clock, multiplying by 3 only ever reaches 0, 3, 6 and 9, and the powers of 3 run 3, 9, 3, 9 without ever landing on 1. The well-behaved numbers are the units: those that share no factor with n. Their count is written φ(n). On a 12-hour clock the units are 1, 5, 7 and 11, so φ(12) = 4.

Euler's theorem (Theorem 2.1.20 in Stein): if x shares no factor with n, then x^φ(n) ≡ 1 (mod n). When n is a prime p, every number from 1 to p − 1 is a unit, so φ(p) = p − 1, and the statement becomes Fermat's little theorem: a^p−1 ≡ 1 (mod p) for every a the clock does not treat as 0.

Why? Keep multiplying by a and the powers must eventually repeat, because the clock has only finitely many positions. The first power that returns to 1 is called the order of a. The units form a group, and Lagrange's theorem says an element's order always divides the size of the group. So on a prime clock the powers of any a come back to 1 after p − 1 steps, or after some divisor of p − 1. Mod 7, the powers of 3 run 3, 2, 6, 4, 5, 1 — six steps. The powers of 2 run 2, 4, 1 — three steps, and 3 divides 6. The book also proves the theorem a second time, from first principles.

A test for primes, and its trap

Turn the theorem round. Stein's Theorem 2.4.1: a number p > 1 is prime if and only if a^p−1 ≡ 1 (mod p) for every a not ≡ 0. One failure is proof of compositeness. The book's example: 2³²² mod 323 is 157, not 1, so 323 is not prime — and the calculation says nothing about the factors, 17 and 19.

The converse needs every base, and for a large number nobody can try them all, so this test alone cannot prove a number prime. Passing for a few bases proves nothing. The book loosely calls such a number a pseudoprime: it only "seems likely" to be prime. Some composites go further. A Carmichael number is composite yet passes for every base that shares no factor with it. The first is 561 = 3 · 11 · 17, and there are infinitely many. We checked 561 directly: all 320 bases coprime to it pass. The only bases that expose it are the 240 that share one of its factors — and hitting one of those is simply stumbling on a factor.

In short

Clock arithmetic keeps remainders. On a prime clock, the powers of any non-zero number return to 1 within p − 1 steps — Fermat's little theorem, the prime case of Euler's. A number that fails the test for one base is certainly composite. One that passes for a few bases is only a suspect, and 561 passes for every base that shares no factor with it.