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 L=LCM of 1st 16 natural numbers
we have to find minimum positive k such that
(kL-1) mod 17=0
=> kL mod 17=1
L=16*13*11*9*7*5=16*13*63*55
L mod 17 = (-1)*(-4)*(-5)*4 mod 17 = 5 mod 17
k is multiplicative inverse of L modulo 17
=> (5)(7)mod 17 = 35 mod 17 =1
=> k=7 mod 17 
=> min k=7
minimum no. of sheep = 7*L-1 = 5045039

Edited on July 12, 2008, 2:49 am

Posted by Praneeth on 2008-07-12 02:09:59