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 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 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 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…)

Axes for the Chinese Remainder Theorem

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…

Further reading

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).

About these ads

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

  1. Theorem 26: the first isomorphism theorem « Theorem of the week Says:

    [...] 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 .  [...]

  2. mira Says:

    thank you,
    You helped me a lot!

  3. Number Theory: Lecture 2 « Theorem of the week Says:

    [...] 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 [...]

  4. Number Theory: Lecture 3 « Theorem of the week Says:

    [...] 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.) [...]

  5. Theorem 38: There is a primitive root modulo a prime « Theorem of the week Says:

    [...] 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 [...]

  6. Sutton Trust summer school 2012 « Theorem of the week Says:

    [...] 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. [...]

  7. Sutton Trust summer school 2013 | Theorem of the week Says:

    […] 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. […]

  8. Number Theory: Lecture 2 | Theorem of the week Says:

    […] 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. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 145 other followers

%d bloggers like this: