I’ve been meaning to write this for ages, since it’s a subject that I discussed with my students a while back and I think it’s a really lovely result.
Here’s a game you can play with a friend. Ask your friend to think of a number (whole number!) between 1 and 100. Ask him to divide the number by 11 and tell you the remainder. (So you’re expecting a number between 0 and 10.) Then ask him to divide his original number by 13, and again tell you the remainder. Your job is to tell your friend which number he thought of, using just those two pieces of information. You might like to think about whether you can do that, perhaps by trying some examples.
Let’s try an example together. Hopefully you’ve tried some examples yourself already, but I think it might be helpful to work through one together. Let’s say that the number leaves remainder 7 when divided by 11, and 3 when divided by 13. (I promise I’ve just chosen those numbers off the top of my head — I haven’t worked out yet what the starting number might be!) Our job is to work out what number (between 1 and 100) would leave those remainders, and we hope that there will be exactly one such number. In the language of modular arithmetic, we want to find a number between 1 and 100 such that (mod 11) and (mod 13), and we want to show that there’s only one such number (or we shan’t be sure which number our friend thought of).
I’d like to describe to you a strategy that will work in a quite general setting. There are perhaps more direct ways of tackling problems like this ( is 7 more than a multiple of 11, so it must be of the form for some integer , and then it is also 3 more than a multiple of 13, so …), but I’d like to tell you about a rather more elegant approach, because it generalises nicely and is generally nicer (in my opinion)! It’s also more suitable for using if you want to play the game in real time (rather than having to do some quick scribbling while your friend twiddles his thumbs).
I’m going to tell you about a pictorial way of thinking about this, but I’ll explain it with equations too (so don’t worry if you don’t like the picture). Here’s the picture. (Another test of my drawing skills…)
The horizontal and vertical axes are supposed to represent mod 11 and mod 13 respectively. The point shown is supposed to represent a number that is 7 (mod 11) and 3 (mod 13), since it has coordinates (7, 3).
I hope that picture might make what follows seem like a reasonable sort of strategy to try. Let’s suppose (with no terribly clear reason in mind as to why this would be reasonable) that we can find numbers that correspond to the points (1, 0) and (0, 1) on the picture. That is, let’s say that we can find some with (mod 11) and (mod 13), and some with (mod 11) and (mod 13).
How would that help? Well, inspired by either the picture or the congruences, we could then consider the number . The properties of and would mean that then we’d have (mod 11) and (mod 13) — so we’d have a number that satisfies the congruences we want! (We’d still need to think about the fact that we want a number between 1 and 100, and that we want there to be a unique one, but we’ll worry about that later.)
So it seems that finding these and would be a good plan. Can we do that? Yes, we can, and we can use an earlier theorem of the week to make it quite easy. Since 11 and 13 are coprime (have highest common factor 1), Bézout’s theorem tells us that there are some integers and so that . Now can we see a number that’s one more than a multiple of 11 and divisible by 13? Sure, is, so let’s put . In the same way, we see that we can put .
This is all fine in theory, but if we’re going to play the game we need to know what and are. Fortunately, the proof of Bézout’s theorem gives us a way to find them: Euclid’s algorithm. Let’s quickly run through that. Euclid’s algorithm gives us
Now we run backwards:
So we can take and . (There are infinitely many other solutions too, but we need only one here.)
Returning to our game, we choose and . Hopefully you remember that the reason for wanting these numbers is that we can build our out of them. If we put
then the way we built it means that (mod 11) and (mod 13). (I suggest you check this for yourself!)
This is all very well and good, but we still haven’t found a number that’s between 1 and 100. However, all is not lost! Let’s think about two solutions to our congruences, say and . What can we say about the relationship between them?
Well, we know that (mod 11) and (mod 11), so (mod 11). That means that 11 divides (just decoding the congruence notation). The same argument (mod 13) shows that 13 divides . Since 11 and 13 are coprime, this means that divides . (This doesn’t work for numbers that aren’t coprime: 4 and 6 both divide 12, but 4 x 6 = 24 doesn’t divide 12.)
To recap: if and are both solutions to the congruences, then they differ by a multiple of 143. And it’s quick to check that if is a solution and if is plus a multiple of 143 then is a solution too. So once we’ve found one solution to the congruences, say , we know them all: for integer .
In our case, this means that the solutions are all of the form for integer . If we take , we get . So 29 is a solution to our original congruences (check this!), and it lies between 1 and 100. Moreover, there can’t possibly be another solution in that range because any two distinct solutions differ by at least 143. Job done!
Now, you may think that your friend would have fallen asleep while you were doing all that. But have a quick look back at what you’d need to do in practice. We’ve worked out and already, and we can use the same numbers each time (as long as we work with the remainders on division by 11 and 13, of course). So all you have to do is take the appropriate combination of those numbers, and then shift it by a multiple of 143 to get a number in the right range. That shouldn’t be too time-consuming.
All this has been talk about a game. What’s the theorem?
Theorem (Chinese Remainder Theorem) Let , , …, be pairwise coprime numbers greater than 1, and let , , …, be any integers. Then there is some such that (mod ) , …, (mod ), and moreover is unique (mod ).
(Pairwise coprime means that any two of the numbers are coprime. For example, 3, 4 and 5 are pairwise coprime, whereas 3, 4 and 6 are not.)
How does this relate to what we did earlier? We essentially proved this theorem in the case that , , , and : we showed that there’s some so that (mod 11) and (mod 13), and this solution is unique up to a multiple of 143 (any two solutions differ by a multiple of 143).
The general theorem can be proved in the same way, although I might have more difficulty drawing a -dimensional picture. But the same strategy works: find numbers corresponding to basis vectors (in the 3-dimensional case these would be (1, 0, 0), (0, 1, 0) and (0, 0, 1)) and then take a suitable combination. That does the existence part of the proof, and the uniqueness works in the same way as in our case (take two solutions and do the same thing as above to see that they’re the same (mod )).
Why the name? Wikipedia claims that the ancient Chinese used this result to count the soldiers in their army. I have no idea whether this is true, but it’s a good story and I hope it might help my students to remember the theorem!
Oh, and I hope you enjoy impressing your friends with the game…
That Wikipedia page goes on to describe how the theorem can be phrased in more abstract language (such as that of rings), if you like such things. The theorem (in the language I’ve used above) is a classic of introductory number theory, and as such appears in many books, including the one I always mention on these occasions (The Higher Arithmetic, by Davenport).