Remainders of 1, 2, 3, 4Date: 10/09/2001 at 14:10:43 From: Laura Subject: Can Do puzzle question Find the smallest whole number that when divided by 5, 7, 9, and 11 gives remainders of 1, 2, 3, and 4 respectively. Show all work. This involves more than just writing the answer down and dividing. Date: 10/09/2001 at 16:42:28 From: Doctor Jodi Subject: Re: Can Do puzzle question Hi Laura, Thanks for writing us. There's a similar problem answered at Find the Smallest Number - A Remainder Problem http://www.mathforum.org/dr.math/problems/bob.09.27.01.html Take a look and write back if you have more questions or want to discuss your problem some more. - Doctor Jodi, The Math Forum http://mathforum.org/dr.math/ Date: 10/09/2001 at 16:48:37 From: Doctor Greenie Subject: Re: Can Do puzzle question Hello, Laura - The first kind of problem like this typically asks something like "what is the smallest whole number that is divisible by 2, 3, 4, ..., and 9?" For a problem like this, you probably know that you build the answer using the prime factorizations of all the divisors. The first extension of this type of problem is one that asks something like "what is the smallest whole number that leaves a remainder of 1 when divided by 2, 3, 4, 5, or 6?" Using the modulo notation (with "=" being the modulus symbol, since I don't have a "three-bar equals sign" on my keyboard), the information here tells us that, for the number x we are looking for... x = 1 mod 2 x = 1 mod 3 x = 1 mod 4 x = 1 mod 5 x = 1 mod 6 We can re-write this information as x-1 = 0 mod 2 x-1 = 0 mod 3 x-1 = 0 mod 4 x-1 = 0 mod 5 x-1 = 0 mod 6 When we do this, the problem becomes similar to the previous one, except that now "x-1" is the number n which is divisible by 2, 3, 4, 5, and 6, so the answer to the problem is one more than that number n. Another level of difficulty is introduced into this type of problem when the problem asks something like "what is the smallest whole number that leaves remainders of 3, 4, 5, and 6, respectively, when divided by 5, 6, 7, and 8?" Here we have the following information, in modulo notation, about our number x: x = 3 mod 5 x = 4 mod 6 x = 5 mod 7 x = 6 mod 8 We notice here that the remainders are always 2 less than the divisor; another way of expressing this is that the difference between successive divisors is the same as the difference between successive remainders. Because the difference between successive divisors is the same as the difference between successive remainders, we can solve this type of problem by rewriting the given information as x+2 = 5 = 0 mod 5 x+2 = 6 = 0 mod 6 x+2 = 7 = 0 mod 7 x+2 = 8 = 0 mod 8 So we see that here we look for the smallest whole number n that is divisible by 5, 6, 7, and 8; and the answer to the problem is 2 less than the number n. In your problem, yet another element has been added to change the required method of solution. The given information in your problem is the following: x = 1 mod 5 x = 2 mod 7 x = 3 mod 9 x = 4 mod 11 Here, the remainder only increases by 1 each time the divisor increases by 2. We would like to find a way to re-write this information in such a way that the remainder increases by 2 each time the divisor increases by 2 - so that the problem looks like the preceding one. We can do this by getting really clever here and rewriting the given information as follows: 2x = 2 mod 5 2x = 4 mod 7 2x = 6 mod 9 2x = 8 mod 11 The idea here is actually quite simple: we had the information that, for the number x we are looking for, the remainders increased by 1 each time the divisor increased by 1; by doubling our number to 2x, we will get remainders that increase by 2 each time the divisor increases by 2. Then we can solve the problem by the method we used on the preceding problem, by re-writing the given information again as follows: 2x+3 = 5 = 0 mod 5 2x+3 = 7 = 0 mod 7 2x+3 = 9 = 0 mod 9 2x+3 = 11 = 0 mod 11 The solution to the problem is then found by first finding the number n that is the smallest whole number divisible by 5, 7, 9, and 11; then the answer to the problem is the number x for which n = 2x+3. I hope you can follow all this, and that it helps. Please write back if you have further questions on this. - Doctor Greenie, The Math Forum http://mathforum.org/dr.math/ Date: 11/11/2001 at 23:02:53 From: Doctor Peterson Subject: Re: Remainders Here's a quick hint. I first notice that when the divisor increases by 2, the remainder increases by 1. I am aware of a similar kind of problem where the remainder increases by 1 when the divisor increases by only 1, which has an almost easy solution. (Easy when you see it!) This problem can be transformed to that kind by thinking about 2x rather than x, the number we're looking for. We can express the statements about remainders by saying that there are integers a, b, c, and d for which x = 5a + 1 x = 7b + 2 x = 9c + 3 x = 11d + 4 Now double each of these equations: 2x = 5(2a) + 2 2x = 7(2b) + 4 2x = 9(2c) + 6 2x = 11(2d) + 8 I did that so that the remainders are now counting by twos, as the divisors are. That lets me use the trick I know: since each remainder is now 3 less than the corresponding divisor, I can add 3 to both sides and eliminate remainders entirely: 2x + 3 = 5(2a) + 5 = 5(2a+1) 2x + 3 = 7(2b) + 7 = 7(2b+1) 2x + 3 = 9(2c) + 9 = 9(2c+1) 2x + 3 = 11(2d) + 11 = 11(2d+1) This tells use that 2x+3 is a multiple of 5, 7, 9, and 11. (We don't need to worry about what a, b, c, and d are.) Find the smallest number that fits that, and then solve to find x. - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/