Smallest Number PuzzleDate: 06/30/98 at 03:11:58 From: Dr. H. M. Behl Subject: Find the smallest number... Dear Dr. Math, One problem: Find the smallest number which when divided by 9,13,17, and 25 leaves remainders 1,0,2, and 3 respectively. Thank you. Rohit Behl Date: 06/30/98 at 08:09:41 From: Doctor Anthony Subject: Re: Find the smallest number... The relevant equations are: x - 1 = 9p ......(1) x = 13q ......(2) x - 2 = 17r ......(3) x - 3 = 25s ......(4) where p, q, r and s are integers. Solving (1) and (2) we get 13q - 1 = 9p which must be solved in integers for p and q. This requires p = 13k - 3 and q = 9k - 2 where k is ANY integer. A similar exercise with (2) and (3) requires r = 13k' + 6 q = 17k' + 8 Now solve in integers k and k' the two values of q, namely q = 17k' + 8 = 9k - 2 This leads to k = 17t + 20 where t is an integer and q = 153t + 178 Finally we solve (2) and (4) getting s = 13u + 3 and q = 25u + 6, so now we require solution in integers u and t of q = 25u + 6 = 153t + 178 This gives t = 25k'' + 176 and putting k'' = -7 we get t = 1. Putting t = 1 into q = 153t + 178 gives q = 331 and so x = 13q = 4303 and this will be the required number. So the smallest number which when divided by 9, 13, 17, and 25 leaves remainders 1, 0, 2, and 3 is 4303 4303/9 = 478 + 1/9 4303/13 = 331 4303/17 = 253 + 2/17 4303/25 = 173 + 3/25 - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 07/02/98 at 07:25:34 From: Doctor Floor Subject: Re: Find the smallest number... Hi Rohit, I suppose you want to have the smallest _positive_ number that has remainders 1, 0, 2, and 3 when divided by 9, 13, 17, and 25 respectively. Since the remainder after division by 13 has to be 0, we know that the number N we are looking for must be a multiple of 13. Thus for some n we know that N = 13n. The next step is to try to make n in such a way that 13n = 9x+1 for some x, so that the remainder after dividing by 9 will be 1. By trying we search for the smallest n for which this works. That gives n = 7, resulting in x = 10. But that does not yet give all possible n. Think of a second number n, not equal to 7, that makes 13n = 9y+1 for some y. Then: 13n - 13*7 = 9y + 1 - 91 13*(n-7) = 9y - 90 13*(n-7) = 9*(y-10) But then, since 13 and 9 have 1 as Greatest Common Multiple (13 and 9 are coprime), n-7 must be a multiple of 9. Or n = 9m+7 for some m. So we are sure now that n must be of the form n = 9m+7, but we have not yet checked whether any m works. If we take n = 9m+7 for some m, then 13(9m+7) = 117m+91 = 9X+1 for some X. So indeed any m works. Conclusion: N = 13n = 13(9m+7) = 117m+19 makes n a multiple of 13 and 1 plus a multiple of 9. In the same way you can look for the values for m that make 117m+91 = 17y+2 for some y. And you should find that m = 17k+2. This results in N = 117(17k+2)+91 = 1989k+325 for some k. In the end, again in the same way, you can look for values of k to make 1989k+325 = 25z+3 for some z. Well, only the smallest k is needed. I think you must be able to find this by yourself now. I hope to have been of help. Best regards, - Doctor Floor, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/