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.
What is the minimum number of sheep he has?
Let the number of sheep the farmer possesses be N. By the problem, dividing N by 2, 3, 4, ....., 15, 16 in turn, a remainder of -1 is obtained in each case.
Thus, N = m*LCM(2,3,4,.....,15, 16) - 1
0r, N = 720,720*m - 1, whenever m is a positive integer
Since by the problem, N is evenly divisible by 17, we must have:
720,720*m (mod 17) = 1
or, 5*m (mod 17) = 1(mod 17) = 35
or, m (mod 17) = 7
or, m = 17*p + 7, where p is a nonnegative integer.
or, N = 720,720(17*p + 7) - 1
= 12,252,240*p + 5,045,039
The minimum value of N occurs whenver p = 0, giving: N = 5,045,039
Consequently, the required minimum number of sheep is 5,045,039.
Edited on July 11, 2008, 11:38 am
Solution
