The Smallest Number Which When Divided Leaves Specific Remainders
Date: 02/27/2010 at 08:32:22 From: Sonal Subject: Divisibility 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.
Date: 02/27/2010 at 18:28:22 From: Doctor Rick Subject: Re: Divisibility 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! 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.) 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. 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! 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. - Doctor Rick, The Math Forum http://mathforum.org/dr.math/
Date: 02/28/2010 at 00:57:03 From: Sonal Subject: Divisibility Hi Dr. Rick, 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. Regards, Sonal
Date: 02/28/2010 at 16:35:37 From: Doctor Rick Subject: Re: Divisibility 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. - Doctor Rick, The Math Forum http://mathforum.org/dr.math/
Date: 03/01/2010 at 01:10:28 From: Sonal Subject: Thank you (Divisibility) Hi Dr. Rick, 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. Regards, Sonal * * * * * * * * * * * * * * * * * * Hi Dr. Rick, 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)
Date: 03/01/2010 at 17:08:37 From: Doctor Rick Subject: Re: Thank you (Divisibility) 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! 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. - Doctor Rick, The Math Forum http://mathforum.org/dr.math/
Date: 03/01/2010 at 22:01:26 From: Sonal Subject: Divisibility Hi Dr. Rick, 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)
Date: 03/01/2010 at 22:35:28 From: Doctor Rick Subject: Re: Divisibility Hi, Sonal. 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. - Doctor Rick, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.