Group Sizes and Remainders
Date: 05/19/2002 at 12:49:55 From: Jonathan Subject: Sheep puzzle A farmer has some number of sheep and needs to divide them into equal groups. He tries groups of 2, but finds he has 1 left over. Then he tries groups of 3, but has 2 left over. Then he tries groups of 4, but has 3 left over...and so on, until he gets to groups of 17, and the sheep fit perfectly. How many sheep are there? Obviously it has to be a multiple of 17 and will end in a 9 as groups of ten lead to 9 left over. I would be very grateful to find out the answer.
Date: 05/19/2002 at 17:51:07 From: Doctor Rick Subject: Re: Sheep puzzle Hi, Jonathan. This farmer is a big businessman! The answer I get is 5,045,039 sheep. I got this by first considering the remainders if he had n+1 sheep. This allows me to say that n+1 is a multiple of a particular number. Then all you have to do is to test each multiple of that particular number I found, starting with the number itself, to see which is one more than a multiple of 17. If you want to find ALL the solutions (there is an infinite number of them), you can write a linear diophantine equation and solve it using methods found in the Dr. Math Archives. - Doctor Rick, The Math Forum http://mathforum.org/dr.math/
Date: 05/20/2002 at 11:55:57 From: Doctor Anthony Subject: Re: Sheep puzzle Suppose there are n sheep. Then n = 17a and n = 16b-1 = 15c-1 = 14d-1 = 13e-1 = 12f-1 and so on. So n+1 = 16b = 15c = 14d = 13e = 12f and so on. So n+1 must be a multiple of 2, 3, 4, 5, 6, 7, ..., 16 We require n+1 = 2^4 x 3^2 x 5 x 7 x 11 x 13 x k where k is some other integer. So n+1 = 720720k n = 720720k - 1 = 17a We require integer solutions of 17a - 720720k = -1 To find them, divide by the smaller coefficient (17) to get a - 42395k - 5k/17 = -1/17 a - 42395k = (5k-1)/17 So (5k-1)/17 must be an integer, say t: 5k-1 = 17t k = (17t+1)/5 Trying values of t, we find that t=1 doesn't work, but t=2 gives us a value of k=7. This means that n = 720720k - 1 = 5045040 - 1 = 5045039 and if you check this number it leaves a remainder 1 less than the divisor on division by 2, 3, ....., 16 and is exactly divisible by 17. - Doctor Anthony, 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.