Theorem 24: the Chinese remainder theorem

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 them to divide the number by 11 and tell you the remainder. (So you’re expecting a number between 0 and 10.) Then ask your friend to divide the original number by 13, and again tell you the remainder. Your job is to tell your friend which number they 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 $N$ between 1 and 100 such that $N \equiv 7$ (mod 11) and $N \equiv 3$ (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 ( $N$ is 7 more than a multiple of 11, so it must be of the form $N = 11k + 7$ for some integer $k$ , 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 friends twiddle their 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 $x_{11}$ with $x_{11} \equiv 1$ (mod 11) and $x_{11} \equiv 0$ (mod 13), and some $x_{13}$ with $x_{13} \equiv 0$ (mod 11) and $x_{13} \equiv 1$ (mod 13).

How would that help? Well, inspired by either the picture or the congruences, we could then consider the number $N = 7 x_{11} + 3 x_{13}$ . The properties of $x_{11}$ and $x_{13}$ would mean that then we’d have $N \equiv 7$ (mod 11) and $N \equiv 3$ (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 $x_{11}$ and $x_{13}$ 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 $h$ and $k$ so that $11h + 13k = 1$ . Now can we see a number that’s one more than a multiple of 11 and divisible by 13? Sure, $13k$ is, so let’s put $x_{11} = 13k$ . In the same way, we see that we can put $x_{13} = 11h$ .

This is all fine in theory, but if we’re going to play the game we need to know what $h$ and $k$ 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

$13 = 1 \times 11 + 2$

$11 = 5 \times 2 + 1$ .

Now we run backwards:

$1 = 11 - 5\times 2 = 11 - 5 \times (13 - 1 \times 11) = 6 \times 11 - 5 \times 13$ .

So we can take $h = 6$ and $k = -5$ . (There are infinitely many other solutions too, but we need only one here.)

Returning to our game, we choose $x_{11} = 13k = -65$ and $x_{13} = 11h = 66$ . Hopefully you remember that the reason for wanting these numbers is that we can build our $N$ out of them. If we put

$N = 7 x_{11} + 3x_{13} = -7 \times 65 + 3 \times 66 = - 455 + 198 = -257$ ,

then the way we built it means that $N \equiv 7$ (mod 11) and $N \equiv 3$ (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 $N$ and $N'$ . What can we say about the relationship between them?

Well, we know that $N \equiv 7$ (mod 11) and $N' \equiv 7$ (mod 11), so $N \equiv N'$ (mod 11). That means that 11 divides $N - N'$ (just decoding the congruence notation). The same argument (mod 13) shows that 13 divides $N - N'$ . Since 11 and 13 are coprime, this means that $11 \times 13 = 143$ divides $N - N'$ . (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 $N$ and $N'$ are both solutions to the congruences, then they differ by a multiple of 143. And it’s quick to check that if $N$ is a solution and if $N'$ is $N$ plus a multiple of 143 then $N'$ is a solution too. So once we’ve found one solution to the congruences, say $N$ , we know them all: $N + 143k$ for integer $k$ .

In our case, this means that the solutions are all of the form $-257 + 143k$ for integer $k$ . If we take $k = 2$ , we get $-257 + 2\times 143 = 29$ . 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 $x_{11}$ and $x_{13}$ 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 $n_1$ , $n_2$ , …, $n_k$ be pairwise coprime numbers greater than 1, and let $a_1$ , $a_2$ , …, $a_k$ be any integers. Then there is some $N$ such that $N \equiv a_1$ (mod $n_1$ ) , …, $N \equiv a_k$ (mod $n_k$ ), and moreover $N$ is unique (mod $n_1 \times n_2 \times \dotsm \times n_k$ ).

(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 $k=2$ , $n_1 = 11$ , $n_2 = 13$ , $a_1 = 7$ and $a_2 = 3$ : we showed that there’s some $N$ so that $N \equiv 7$ (mod 11) and $N \equiv 3$ (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 $k$ -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 $n_1 \times \dotsm \times n_k$ )).

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…

11 Responses to “Theorem 24: the Chinese remainder theorem”

Theorem 26: the first isomorphism theorem « Theorem of the week Says:
May 20, 2010 at 11:35 pm
[…] slightly more interesting example. We also have groups and . One special case of the Chinese Remainder Theorem says that is isomorphic to the product . We could prove that by defining a map from to . […]
mira Says:
February 26, 2011 at 9:25 pm
thank you,
You helped me a lot!
Number Theory: Lecture 2 « Theorem of the week Says:
October 10, 2011 at 12:03 pm
[…] studying the structure of and next time. This would be a good time to remind yourself of the Chinese Remainder Theorem, and to try to see what it tells us about and . If you like, you could start by considering […]
Number Theory: Lecture 3 « Theorem of the week Says:
October 14, 2011 at 12:18 pm
[…] Theorem 9 (Chinese Remainder Theorem): Let and be coprime natural numbers greater than 1, and let and be integers. Then there is a solution to the simultaneous congruences , , and moreover this solution is unique modulo . We saw that if (where the are distinct primes), then and are isomorphic as rings. (So we can sometimes reduce problems to studying behaviour modulo powers of primes.) […]
Theorem 38: There is a primitive root modulo a prime « Theorem of the week Says:
October 23, 2011 at 4:32 pm
[…] out that if is an odd prime then there is a primitive root modulo any power of , and thanks to the Chinese Remainder Theorem this gets us a long […]
Sutton Trust summer school 2012 « Theorem of the week Says:
August 16, 2012 at 11:47 am
[…] In the first lecture, we talked about Euclid‘s algorithm and Bézout‘s lemma. In the second, we mentioned the Fundamental Theorem of Arithmetic, and we learned about modular arithmetic. In the third and final lecture, we mentioned that is irrational, and talked about continued fractions. There are many proofs that is irrational. We mentioned that there are many more irrational numbers than rational; that’s because the rationals are `countable’, whereas the irrationals are `uncountable’. A couple of the problems on the examples sheet are related to the Chinese Remainder Theorem. […]
Sutton Trust summer school 2013 | Theorem of the week Says:
August 15, 2013 at 9:11 am
[…] In the first lecture, we talked about Euclid‘s algorithm and Bézout‘s lemma. In the second, we mentioned the Fundamental Theorem of Arithmetic, and we learned about modular arithmetic. In the third and final lecture, we mentioned that is irrational, and talked about continued fractions. There are many proofs that is irrational. A couple of the problems on the examples sheet are related to the Chinese Remainder Theorem. […]
Number Theory: Lecture 2 | Theorem of the week Says:
October 14, 2013 at 10:15 am
[…] Theorem 9 (Chinese Remainder Theorem): Let and be coprime natural numbers greater than , and let and be integers. Then there is a solution to the simultaneous congruences and , and moreover this solution is unique modulo . We proved the existence part of this by finding and such that and and and and then taking a suitable linear combination. We did the uniqueness part on autopilot. […]
newton kibogot Says:
March 2, 2015 at 5:18 pm
thank you it is very helpful information
Groups and Group Actions: Lecture 6 | Theorem of the week Says:
March 6, 2015 at 11:06 am
[…] lemma (or theorem or whatever) before on this blog. I’ve also written about the Chinese Remainder Theorem, phrased in a different way. Linking that version of the theorem with the group theory one we saw […]
Groups and Group Actions: Lecture 6 | Theorem of the week Says:
March 3, 2016 at 10:09 am
[…] lemma (or theorem or whatever) before on this blog. I’ve also written about the Chinese Remainder Theorem, phrased in a different way. Linking that version of the theorem with the group theory one we saw […]

Theorem of the week