eli5: How does the Chinese remainder theorem work?
In: Mathematics
Let’s pick a pair of numbers: 3 and 10. Notice that these are *relatively prime*, meaning that they don’t have any common factors other than 1. We’ll get to that later, but for now just keep it in mind.
Now let’s say you take any integer at all, call in K, and divide it by each of our numbers. We don’t care what the result of the division is – only the remainders. What are the options for the remainders?
When we divide K by 3, the remainder is either 0, 1, or 2. When we divide it by 10, the remainder could be any of [0,1,2, … 9]. How many options are there, if we look at the combination of both remainders?
Well we saw that the 3 remainder is one of 3 options, and the 10 remainder is one of 10 options. So if you pair them up, it could be one of 3*10 = 30 total options for the pair. I’ll list some here with the 3 remainder and then the 10 remainder:
(0, 0)
(1, 0)
(2, 0)
(0, 1)
(1, 1)
(2, 1)
…
(0, 9)
(1, 9)
(2, 9)
Notice that the number of possibilities is exactly equal to the product of our numbers, 3*10. This isn’t a coincidence. You should be able to try out a few more examples and convince yourself that this is always true.
Now, to make things simple, let’s take a look at some possible values for K. Let’s only consider numbers for K that are between 1 and 30 (the product of our numbers). We know that whichever K we pick, we can figure out its 3-remainder and its 10-remainder, and the combination will be one of our 30 pairs.
This leads to a natural curious question: does each number get a *different* combination?? Or do some of the numbers have the same pair of remainders? Because there are 30 options now for K and 30 options for the remainder pair, this is the same as asking “Does every remainder pair have a K?”.
The answer, it turns out, is **yes** – each option for K gives a unique remainder pair, and each remainder pair does have a K that leads to it. Let’s have a look:
(0, 0) : [30]
(1, 0) : [10]
(2, 0) : [20]
(0, 1) : [21]
(1, 1) : [1]
(2, 1) : [11]
(0, 2) : [12]
(1, 2) : [22]
(2, 2) : [2]
(0, 3) : [3]
(1, 3) : [13]
(2, 3) : [23]
(0, 4) : [24]
(1, 4) : [4]
(2, 4) : [14]
(0, 5) : [15]
(1, 5) : [25]
(2, 5) : [5]
(0, 6) : [6]
(1, 6) : [16]
(2, 6) : [26]
(0, 7) : [27]
(1, 7) : [7]
(2, 7) : [17]
(0, 8) : [18]
(1, 8) : [28]
(2, 8) : [8]
(0, 9) : [9]
(1, 9) : [19]
(2, 9) : [29]
We can see that each number K (on the right) has a different remainder combo (on the left)!! I’ve ordered them in this way so that you can more easily see some patterns. Notice that the 10-remainder is just the last digit of the number. That should make sense.
But let’s look at, say, 9, 19, and 29. We know they all have 9 as their 10-remainder. What about their 3-remainders? Could any of them have been the same? The answer is no, and you may need to look at more examples to convince yourself of this.
To help, notice that 9 has a 3-remainder of 0, and the difference between 9 and the other numbers is either 10 or 20 – neither of which is a multiple of 3! This is true for 7, 17, and 27 also, and you should see that it is true in general!
We haven’t rigorously proven yet that this *always* happens, but you should start to feel the intuition here. A good exercise right now is to try it again for another pair of numbers. Let’s try 6 and 10:
(0, 0) : [30, 60]
(2, 0) : [20, 50]
(4, 0) : [10, 40]
(1, 1) : [1, 31]
(3, 1) : [21, 51]
(5, 1) : [11, 41]
(0, 2) : [12, 42]
(2, 2) : [2, 32]
(4, 2) : [22, 52]
(1, 3) : [13, 43]
(3, 3) : [3, 33]
(5, 3) : [23, 53]
(0, 4) : [24, 54]
(2, 4) : [14, 44]
(4, 4) : [4, 34]
(1, 5) : [25, 55]
(3, 5) : [15, 45]
(5, 5) : [5, 35]
(0, 6) : [6, 36]
(2, 6) : [26, 56]
(4, 6) : [16, 46]
(1, 7) : [7, 37]
(3, 7) : [27, 57]
(5, 7) : [17, 47]
(0, 8) : [18, 48]
(2, 8) : [8, 38]
(4, 8) : [28, 58]
(1, 9) : [19, 49]
(3, 9) : [9, 39]
(5, 9) : [29, 59]
Oh crap. This didn’t work. Is the Chinese Remainder Theorem wrong after all these centuries?
No, we made a mistake. 6 and 10 are not relatively prime – they share 2 as a divisor. It doesn’t work when the numbers aren’t relatively prime. Looking at the list, you may start to get some intuition as to why: if a number has a remainder of 0 when you divide it by 10, then it *has* to be an even number. That means it can’t have a remainder of 1 when you divide it by 6. So some of the combinations cannot exist!
At this point, rather than going into a rigorous proof of why this works, I would just encourage you to try it out for some other numbers. We used 10 here because it makes some of the math easier to see, but this will work just as well if you choose 3 and 5, or 5 and 6, or any other pair of relatively prime numbers.
There are two final details, that shouldn’t be too hard to accept if you’re comfortable with everything so far.
First, in the 3&10 example we only considered numbers between 1 and 30. What about the others? Well it’s pretty easy to show that if you take a different number, like 37, and you want to know its remainder combination, you can just divide the number by 30 and take the remainder – so in this case 7, and it will have the same remainder pair as 7 did.
Second, we always picked two numbers (3 and 10, 6 and 10, etc). It also works for more than two numbers! They *all* have to be relatively prime to each other (we would usually say that they are all *coprime*, which is just another word for *relatively prime*), but it works if they are!
Finally, how to *use* the theorem if somebody gives you a bunch of remainders and asks you to find the number. Let’s say that someone says “the remainder of my number when divided by 3 is 2 and the remainder when divided by 10 is 7”.
We could just go look in my table up there and see that the answer is 17. But that would take a long time in general, since you have to go compute every pair ahead of time to make the table. Instead, why don’t we start listing the numbers that have a 3-remainder of 2:
2, 5, 8, 11, 14, 17, 20, 23, 26, 29
As we list them, we can just check each one to see if it has a 10-remainder of 7. Obviously we will achieve that at when we get to 17. **The Chinese Remainder Theorem tells us that because 3 and 10 are relatively prime, when we hit 17, we can stop looking for any more solutions.** We can say with certainty that the number is either 17 or it is of the form (17 + 30*N) for some integer N (in other words, it could be 47 or 77 or -13 or -43, et cetera). We don’t have to check 20, or 23, or 26, or 29 because we *know* that 17 is the only possible option between 1 and 30.
The method I’ve used here could be better, and I’ll leave it to you to find out why. Instead of starting with the numbers that have the right 3-remainder, it will go faster if I start with the numbers that have the right 10-remainder. In general, if you start with the largest of your numbers first, you’ll find the correct answer faster. Try it out to see why!
Latest Answers