Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search