The Chinese Remainder Clock

# The Chinese Remainder Theorem

With clocks, we consider different numbers as if they were the same. For instance, in a 12-hours clock, the 12 is identified with 0, the 13 is identified with 1, and so on. We can also say that 11 is identified with -1. In mathematics, we call this identification "numbers modulo 12", and we write 12=0 mod 12 to make it shorter. We can consider numbers modulo m for any natural number m (at least 2), for instance, numbers modulo 2 means that 0=2=-2=4=-4=... mod 2, and 1=-1=3=-3=... mod 2, so all the even numbers are equivalent to 0, and all the odd numbers are equivalent to 1. All numbers modulo m are equivalent to some number from 0 to m-1. To find what is the equivalent of a number modulo m, we divide it (integer division, no decimals) by m and we keep the remainder.

We can compare numbers modulo m by varying m. Indeed, if d divides m, then a number modulo m gives a number modulo d: we just divide the given number by d and keep its remainder. For example, 8 modulo 12 gives 2 modulo 3 and 0 modulo 4.

Drag the hands to see the correspondences.

The Chinese Remainder Theorem says that, conversely, each pair of numbers modulo 3 and modulo 4 arises from one and only one number modulo 12. So we have a perfect correspondence between the numbers modulo 12 and the pairs of numbers modulo 3 and modulo 4. In other words, instead of giving a number modulo 12 (as for the hours in a usual clock) we can give a pair of numbers modulo 3 and modulo 4 (as for the hours in the Chinese Remainder Clock). When do we have that perfect correspondence? Clearly, if we want numbers modulo m to be splitted into pairs of numbers modulo a and modulo b, we need that m = a x b, otherwise the two sets have a different number of elements. But is that enough? Let's see the next example.

Drag the hands to see the correspondences. Try first using as input the 12-hours clock, and then use as input the 2-hours and 6-hours clocks.

If we try to split numbers modulo 12 into numbers modulo 2 and modulo 6, we have a problem. We can always "read" a number modulo 12 in modulo 2 or modulo 6. However, the number 0 mod 12 and the number 6 mod 12 both correspond to (0 mod 2 , 0 mod 6). At the same time, no number modulo 12 corresponds to (1 mod 2, 0 mod 6), because all numbers equivalent to 0 mod 6 are multiples of 6, and therefore they are even numbers, and all even numbers are equivalent to 0 mod 2, not 1 mod 2. This means that there is no perfect correspondence between the numbers modulo 12 and the pairs of numbers modulo 2 and modulo 6. The reason is that 2 and 6 have a common factor.

The Chinese Remainder Theorem says the following:

Theorem. Let m be a natural number which is at least 2. Let a and b be natural numbers such that m = a x b. Assume that a,b have no common factors. Then each pair of numbers modulo a and modulo b arises from one and only one number modulo m.

This is the theorem that the Chinese Remainder Clock uses to display hours (hours in modulo 3 and modulo 4 replace the usual hours in modulo 12). Similarly, we can generalize to more than two moduli.

Theorem. Let m be a natural number which is at least 2. Let a,b, and c be natural numbers such that m = a x b x c. Assume that a,b have no common factors, and that the same holds for a,c and b,c. Then each triple of numbers modulo a, modulo b, and modulo c arises from one and only one number modulo m.

For example, the numbers modulo 60 (minutes in the usual clocks) are in perfect correspondence with the triples of numbers modulo 3, modulo 4, and modulo 5 (minutes in the Chinese Remainder Clock).