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/