(An archive question of the week)
My title is tongue-in-cheek, as we’ll be looking at the Chinese Remainder Theorem, which is really a Chinese theorem about remainders, not a theorem about “Chinese remainders”. But we’ll work on a problem that can be solved with or without knowledge of the theorem, and with various doses of number theory techniques. This is an interesting example of dialogue, exploring multiple ways to approach a problem at multiple levels.
The problem
Here is the initial question, from 11-year-old Sonal in 2010:
The Smallest Number Which When Divided Leaves Specific Remainders What is the smallest number which when divided by 3, 7, and 11 leaves remainders 1, 6, and 5, respectively? I understand that this involves least common multiple, but have found only that 3, 7, and 11 have differences of 4, and cannot figure out any further.
To make sure you follow what the question asks for, suppose the answer was 123. To check it, we would divide it by each of the three divisors, and find that 123 ÷ 3 = 41 r 0; 123 ÷ 7 = 17 r 4; and 123 ÷ 11 = 11 r 2. Since the remainders are 0, 4, and 2 rather than 1, 6, and 5, this doesn’t work.
An intelligent search
This type of problem is a classic, with a theorem of its own; but Doctor Rick presumed that Sonal would need a more elementary answer:
Hi, Sonal. There are some high-powered math tools that can be used to solve problems like this -- things like the Chinese Remainder Theorem and the Extended Euclidean Algorithm. I doubt very much that you have learned these things! At the other end of the spectrum of ways to solve this problem is the direct approach -- "brute-force": Go through all the whole numbers starting from 1, finding the remainders until you find a number that works. That's sure to work, but it's sure to be tedious!
It’s often worth pointing out such a brute-force method, if only to remind students that problems can legitimately be solved without fancy methods. “Trial-and-error” is a valid method, even if it may (sometimes) be less efficient than others; and if done well, it can even be as “mathematical” and thoughtful as formal methods.
We can find an in-between method that will do the trick without requiring advanced math, but first I'll show you one idea that helps us know the brute-force search won't go on forever. If you take any number and add the LCM of 3, 7, and 11 to it, both these numbers will, on division by 3, 7, and 11, have the same remainders. The LCM is a multiple of 3, and adding a multiple of 3 doesn't change the remainder on division by 3. Likewise, it is a multiple of 7 and of 11, so adding that LCM doesn't change the remainders on division by 7 or 11, either. This means that we only have to check the numbers up to the LCM, which is 3 * 7 * 11 = 231. After that, the pattern of remainders will start to repeat, and we'll only see things we've seen before. If we haven't found an answer by the time we reach 231, we never will. (In fact, the Chinese Remainder Theorem tells us that we WILL find an answer.)
Knowing a problem has a solution is sometimes half the battle! We have now limited the total size of our search: 1, 2, 3, 4, …, 231
Now for the first idea to shorten the search. We could make a list of numbers that are 5 more than a multiple of 11: 5, 16, 27, ... Do you see that we can just keep adding 11 each time? The list will only be 3 * 7 = 21 numbers long, which is a lot easier to search through than a list of 231 numbers. And we only need to test their remainders on division by 3 and 7.
Why did he start with multiples of 11 rather than 3 or 7? Because that will leave us with fewer numbers to try. Now our search is even shorter: 5, 16, 27, 38, 49, 60, 71, 82, 93, 104, 115, 126, 137, 148, 159, 170, 181, 192, 203, 214, 225. We could just divide each of these by 7 and discard those whose remainder is not 6; then divide the remaining numbers by 3 and look for one whose remainder is 1.
But we can do better! Let's apply the same idea about a repeating pattern of remainders to a smaller problem: finding numbers that give a remainder of 1 when divided by 3, and that give a remainder of 6 when divided by 7. The remainder pattern repeats after LCM(3, 7) = 21. By starting with a list of numbers that are 6 more than a multiple of 7, we only need to test three numbers. Can you see which three numbers, and what you test them for? Now, every 21st whole number will have the same remainders when divided by either 3 or 7. Write down these numbers, up to 231; this time, you will need to write down 7 numbers. Test each of these by seeing what remainder they give on division by 11; they already give the correct remainder when divided by 3 or 7. When you find a number that works, you're done!
Let’s finish it up. Abandoning the list of 21 numbers I gave above, we start with 6 and add 7 at a time, stopping when we pass 21, so we have 6, 13, 20. (Those are the three numbers.) The one of these that gives a remainder of 1 on division by 3 is 13.
Now we count from there by 21’s, to make a list of numbers with the right remainders from both 3 and 7: 13, 34, 55, 76, 97, 118, 139, 160, 181, 202, 223. (There are 11 numbers, not 7.) Dividing each of these by 11 and looking for a remainder of 5, we find the answer: 181.
What I have described here is an "intelligent search method." Using facts about numbers, I reduced the "search space" (the set of numbers to be tested) from 231 to 21 numbers, and then to 10, while simplifying the test as well. Isn't that a lot easier? My answer to you is a bit long and I hope you are interested enough to plow through it. To tell the truth, I don't know what method an 11-year-old is expected to use to solve this problem.
The Chinese Remainder Theorem
Sonal wrote back, surprisingly:
Okay, as suggested, I applied the Chinese Remainder Theorem, and found the answer to be 412. The answer was supposed to be of the form ... 77x + 33y + 21z, ... as 77 is the LCM of 7 and 11, 33 is LCM of 3 and 11, and 21 is the LCM of 3 and 7. 77x when divided by 3 should have remainder 1. So x is 2. 33y when divided by 7 should have remainder 6. So y is 4. 21z when divided by 11 should have remainder 5. So z is 6. Thanks for the guidance.
Hmmm … her answer is not what we got above; but she seems to know more than we expected.
Doctor Rick replied:
Hi, Sonal. You are not 11 years old as you said, are you? Had I known, I would not have gone to the trouble of giving you an alternate method. Four hundred and twelve is not the answer I got. The problem was: What is the smallest number which when divided by 3, 7, and 11 leaves remainders 1, 6, and 5, respectively? It's true that: 412 = 1 (mod 3) 412 = 6 (mod 7) 412 = 5 (mod 11) However, 412 is not the smallest positive integer that meets those conditions. The Chinese Remainder Theorem says that the solution is CONGRUENT to 77x + 33y + 21z MODULO 3 * 7 * 11 Since 412 > 3 * 7 * 11, there is a smaller solution.
What is the Chinese Remainder Theorem? The theorem proper, e.g. as presented in Wikipedia, it is just an existence theorem, not explicitly saying how to solve the problem:
Let n1, …, nk be integers greater than 1, which are often called moduli or divisors. Let us denote by N the product of the ni.
The Chinese remainder theorem asserts that if the ni are pairwise coprime, and if a1, …, ak are integers such that 0 ≤ ai < ni for every i, then there is one and only one integer x, such that 0 ≤ x < N and the remainder of the Euclidean division of x by ni is ai for every i.
Since the divisors 3, 7, and 11 are “pairwise coprime” (that is, any two of them have no common factors other than 1), this says that there is exactly one solution to the problem less than the product \(3\times7\times11 = 231\). It doesn’t (in this form) tell how to find that solution; but we can take Sonal’s solution, 412, and find the smallest by subtracting 231 from it until we get a number less than 231, namely 181 (as before).
What about the expression \(77x + 33y + 21z\)? In Wikipedia, Doctor Rick’s method is called Search by Sieving (under Computation), while this method amounts to an application of their Direct Construction proof:
For constructing a solution, it is not necessary to make an induction on the number of moduli. However, such a direct construction involves more computation with large numbers, which makes it less efficient and less used. Nevertheless, Lagrange interpolation is a special case of this construction, applied to polynomials instead of integers.
Let \(N_{i}=N/n_{i}\) be the product of all moduli but one.
As the \(n_{i}\) are pairwise coprime, \(N_{i}\) and \(n_{i}\) are coprime. Thus Bézout’s identity applies, and there exist integers \(M_{i}\) and \(m_{i}\) such that \(M_{i}N_{i}+m_{i}n_{i}=1.\)
A solution of the system of congruences is \(\displaystyle x=\sum _{i=1}^{k}a_{i}M_{i}N_{i}.\)
In fact, as \(N_{j}\) is a multiple of \(n_{i}\) for \(i\neq j,\) we have \(x\equiv a_{i}M_{i}N_{i}\equiv a_{i}(1-m_{i}n_{i})\equiv a_{i}{\pmod {n_{i}}},\) for every \(i.\)
Looking for an easy-to-read source for the approach Sonal took, this is the most concise I found:
We first calculate the \(N_{i}=N/n_{i}\), which are just the products of all but one of the divisors, in our case \(N_{1}=7\cdot11=77\), \(N_{2}=3\cdot11=33\), and \(N_{3}=3\cdot7=21\). Then we find numbers \(M_{i}\), which are the modular inverses of the \(N_{i}\) mod \(n_{i}\); in our case, these are Sonal’s x, y, and z, such that \(77x \equiv 1 (\mod 3)\), \(33x \equiv 1 (\mod 7)\), and \(21x \equiv 1 (\mod 11)\). This is what Sonal did; the hard part is actually finding x, y, and z, which we’ll be looking at below.
Sonal answered, obtaining the correct answer, and explaining the help she had:
Thanks for help in solving the problem. I found the correct answer as 412 - LCM(3, 7, 11), i.e., 412 - 231 = 181. I am indeed 11 years old. I study in standard VI. It is my dad who tried to help me with the Chinese Remainder Theorem, but it looks like he himself has not understood much. He has something to say. So over to him.
Sonal handled that fine. And her dad actually did pretty well. Here is his explanation:
A father’s method
This question is from a maths scholarship question paper set meant for standard VIII. It did not come with any answer, but as per the author of the question paper, this should be solvable by a 13/14 year-old. So in 2 years' time, Sonal is supposed to solve such problems. Sometimes she arrives at the correct answer by applying wrong methods. Here is the method I employed after learning from you that there is a smaller answer than 412. x = 1 (mod 3) (i) x = 6 (mod 7) (ii) x = 5 (mod 11) (iii) (i) => x = 3t +1 (iv) Plugging this value in (ii), 3t + 1 = 6 (mod 7) => 3t = 5 ( mod 7) => t = 4 ( mod 7) => t = 7s + 4 (v) Plugging the value of t from (v) into (iv), x = 3(7s + 4) + 1 = 21s + 13 (vi) So plugging this value of x into (iii), we get 21s + 13 = 5 (mod 11) => 11s + 11 + 10s + 2 = 5 (mod 11) => 10s + 2 = 5 (mod 11) => 10s = 3 (mod 11) => s = 8 (mod 11) => s = 11u + 8 (vii) So plugging this value of x into (iii), we get 21s + 13 = 5 (mod 11) => 11s + 11 + 10s + 2 = 5 (mod 11) => 10s + 2 = 5 (mod 11) => 10s = 3 (mod 11) => s = 8 (mod 11) => s = 11u + 8 (vii) From (vi), x = 21s + 13 = 21(11u + 8) + 13 => x = 231u + 181 => For u = 0, x = 181 So the answer is 181 -- not 412, as we earlier got (for u = 1). Regards, Subhendu (Sonal's Dad)
This method amounts to what Wikipedia describes as solving the problem As a linear Diophantine system.
If you are familiar with modular arithmetic, you will have no trouble seeing what all this means; but at several steps the actual work to obtain certain numbers was omitted.
Doctor Rick answered both father and daughter:
Hi, Sonal. This will be mainly for your dad, but you're welcome to listen in! That's the answer I got, too. Your previous work could give this answer as well. Your solution simply needed to be restated: Every solution is congruent to 412 (mod 231). Then, noting as I did that 412 > 213, we can obtain a smaller positive solution by finding the remainder on division of 412 by 231 -- or by subtracting 231 from 412. There isn't just one correct method (as you know; I think you're saying you used two different methods). I think it's better to help Sonal use what she already understands to solve the problem, rather than introduce math beyond her level; therefore I just named the Chinese Remainder Theorem but didn't go into it. Is the CRT taught to 13/14 year olds in your country? I don't think it is in the US. To tell the truth, though, I am not particularly skilled in number theory, so when I came up with my alternate method, I was thinking not just what an 11 year-old might be able to understand, but what I would rather do myself!
It’s good that the Math Doctors have included people with a wide variety of knowledge, so that some can give deep answers, while others can identify with the student. I’m with Doctor Rick on this topic.
Filling in the details
Doctor Rick continued:
Can you fill in a gap in your explanation of your work? Specifically, how did you make this step? 3t = 5 (mod 7) t = 4 (mod 7) And this one? 10s = 3 (mod 11) s = 8 (mod 11) Unless I'm missing something, filling in those gaps still requires about as much "guess and check" as my method. Here is a similar problem from our Archive: Chinese Remainder Theorem and Modular Arithmetic http://mathforum.org/library/drmath/view/56010.html This shows how to apply the Extended Euclidean Algorithm rather than doing any search. However, such "searchless" methods are not necessarily the best. If the numbers were larger, it would be better; and the algorithm could be implemented in a computer program better than mine.
In case you are unfamiliar with modular arithmetic, the first instance above is looking for a number r such that 3t differs from 5 by a multiple of 7; or, equivalently, the remainder when you divide 3t by 7 will be 5. We can easily check that the answer is valid; \(3\times4 = 12\), and the remainder on division by 7 is indeed 5. But there are several ways this answer can be found. Which way did Subhendu use?
He replied:
The explanation of simplifying 3t = 5 ( mod 7) into t = 4 ( mod 7) goes like this. Any number divided by 7 can have 7 types of remainders: 0 1 2 3 4 5 6 Three times that number will have remainders 0 3 6 2 (3 * 3 = 9, 9 = 7 + 2) 5 (3 * 4 = 12, 12 = 7 + 5) 1 (3 * 5 = 15, 15 = 2 * 7 + 1) 4 (3 * 6 = 18, 18 = 2 * 7 + 4) As 5 corresponds to 4, I have used that relation. As they were all unique, this method worked. Otherwise, I could not have used the same. Simplifying 10s = 3 (mod 11) into s = 8 (mod 11) follows the same kind of reasoning. Regards, Subhendu (Sonal's Dad)
In a sense, this method is trial-and-error – in fact, “try-every-possibility-and-locate-the-one-that-works”.
Doctor Rick concluded:
That's what I thought. You calculated a "multiplication table" in each case, which amounts to trying all the possibilities to see which works out correctly. It turns out quite similar to my method in terms of the work done. I think it's really good to see multiple methods and variations of methods for solving the same problem. Students need to see the creativity in math and that it isn't just following a set method. I enjoy this sort of discussion.
The Extended Euclidean Algorithm
As Doctor Rick said earlier, a more advanced technique, the Extended Euclidean Algorithm, could have been used here, but doesn’t save much work, if any, in a fairly small problem. The problem didn’t really require the heavy equipment of modular arithmetic and big theorems; essentially the same work is done by thinking through the meaning of the problem, with less work needed the more understanding you put into play.
Let’s try that more advanced technique on our problem, for comparison. Recall that we are looking for three numbers x, y, and z, such that \(77x \equiv 1 (mod\ 3)\), \(33x \equiv 1 (mod\ 7)\), and \(21x \equiv 1 (mod\ 11)\). I’ll just do the first of these.
The page Doctor Rick referred to, Chinese Remainder Theorem and Modular Arithmetic, in turn refers to another page, Integer Solutions to \(AX + BY = C\), for the Extended Euclidean Algorithm. Following the instructions there to solve the equation \(77x + 3y = 1\), so that x will be the number that makes \(77x \equiv 1 (mod\ 3)\), we take
\(A = 77\), \(B = 3\), \(u = 1\), \(U = 0\), \(v = 0\), and \(V = 1\).
We divide A by B to find \(77 = 25\cdot3 + 2\), so we have \(q = 25\) and \(r = 2\). Since r is not zero, we take the next step, letting
\(A = B = 3\), \(B = r = 2\), \(u = U = 0\), \(U = u – qU = 1 – 25(0) = 1\),
\(v = V = 1\), and \(V = v – qV = 0 – 25(1) = -25\).
Now we repeat: We divide A by B to find \(3 = 1\cdot2 + 1\), so we have \(q = 1\) and \(r = 1\). Since r is not zero, we take the next step, letting
\(A = B = 2\), \(B = r = 1\), \(u = U = 1\), \(U = u – qU = 0 – 1(1) = -1\),
\(v = V = -25\), and \(V = v – qV = 1 – 1(-25) = 26\).
We repeat again: We divide A by B to find \(2 = 2\cdot1 + 0\), so we have \(q = 2\) and \(r = 0\). Since r is zero, we stop. The solution is \(x = U = -1\) and \(y = V = 26\).
As a check, \(77(-1) + 3(26) = 1\) as required; so the multiplicative inverse of 77 (mod 3) is -1. To get Sonal’s x, we multiply this by the required remainder, 1, to get \(x = -1\).
Is this what Sonal got? Recall that she said
77x when divided by 3 should have remainder 1. So x is 2. 33y when divided by 7 should have remainder 6. So y is 4. 21z when divided by 11 should have remainder 5. So z is 6.
We got \(x = -1\), not 2. Both are right, because this result is (mod 3), and -1 differs from 2 by 3.
Using the same procedure for the other two problems, I find the inverse of 33 (mod\ 7) is 3 (\(33(3) + 7(-14) = 1\)), and \(3\cdot 6 = 18 \equiv 4 (mod\ 7)\) (as Sonal got).
Similarly, the inverse of 21 (mod 11) is -1 (\(21(-1) + 11(2) = 1\)), and \(-1\cdot 5 = -5\equiv 6 (mod\ 11)\).
One more point to make: If we take x as -1, as we got, we would have \(77x + 33y + 21z = 77(-1) + 33(4) + 21(6) = 181\). (Using -5 for z would get us yet another answer congruent to 181.)
This was a similar amount of work to the simple search for inverses. But with larger numbers, this would be a definite improvement, and other techniques would save even more time.