Arithmetic on a Clock

Add four hours to eleven o'clock. The answer is three.

Not fifteen. Not three with an asterisk. Three, because a clock has twelve positions and when you run off the end you continue from the beginning, and the result is a complete and perfectly consistent arithmetic in which fifteen does not exist as an answer.

This is modular arithmetic. Pick a modulus, divide by it, keep the remainder, discard everything else. Mod 12, the numbers are 0 to 11 and nothing else, and 15 and 3 and 27 are all the same number as far as the system is concerned.

The word for that sameness is congruence, and the indifference is the feature rather than a loss to be worked around. Two numbers congruent mod n are interchangeable in every calculation mod n, which means you may replace any awkward number with a small one at any point, and you will often want to.

You have used this more than any other mathematics in this subject.

The last digit of an ISBN is chosen so that a weighted sum of the digits lands on a particular remainder. Mistype one digit and the sum lands somewhere else and the number is rejected before any database is queried. Card numbers use the Luhn check the same way; bank account validation does; so does almost every identifier that has to survive being read aloud or copied by hand. None of it is advertised, and all of it is remainders.

Gauss laid this out in the Disquisitiones Arithmeticae in 1801, aged twenty-four, and invented the congruence notation that is still in use.

He was not thinking about secrets. He was thinking about the structure of the whole numbers, which is as pure as the subject gets, and he was following a question about which numbers divide which. The first public-key cryptosystem is a hundred and seventy-five years later.

That interval is worth noticing because it is normal. The useful thing was not built by someone trying to build it; it was lying around, fully worked out, waiting for a problem that did not yet exist. Hardy boasted in 1940 that number theory had no military application whatsoever and was proud of it. He was wrong within a generation, and the mathematics he was describing is the mathematics that proved him wrong.

One property matters most for what follows.

Because results wrap, they never grow. Raise a number to an enormous power in ordinary arithmetic and the answer has millions of digits and becomes expensive to hold. Do it modulo something and the answer never leaves the fixed range, so a calculation can run a billion steps and stay cheap. Everything in the next two chapters depends on that, and without it none of it would be practical at any scale.