The matter of division of one number by another resulting in a quotient and a remainder is perhaps known by all. It is a piece of knowledge that is universally known and is kind of taken-for-granted. But it is not generally known that this division concept is one of the favorites in creating interesting math puzzles, some of which even reach the status of classics.

In this puzzle session, we will present one such classic puzzle and its variations. As Euclid was reportedly the first to formally record the long known result of division of a number by another, and named the result as division lemma (or theorem), this puzzle based on the matter of division of one number by another may be called Euclid's division lemma puzzle.

Euclid expressed the result of division in the equation,

$\text{Dividend}=\text{Divisor}\times{\text{Quotient}}+\text{Remainder}$,

Or, $a=bq+r$, where $a$ is the dividend, $b$ is the divisor, $q$ is the quotient and $r$ is the remainder.

The strict relationship between the divisor and the remainder is,

Remainder must be less than the divisor and greater than or equal to 0.

*Let us state the puzzle for you solve.*

### Euclid's division lemma puzzle on Counting of eggs

This is a rich folk puzzle based on Euclid's division lemma. We will use a concise version of the original puzzle without compromising its challenge. Reportedly this puzzle appeared first in a book by A. Rampal and others.

#### The puzzle in brief

A trader selling eggs in a village had a quarrel with a man who pulled down the egg basket breaking all the eggs. The trader appealed to the Panchayat for compensation from the offender. When the Panchayat asked the trader how many eggs were broken, the trader replied,

If counted in pairs, one will be left;

If counted in threes, two will be left;

If counted in fours, three will be left;

If counted in fives, four will be left;

If counted in sixes, five will be left;

If counted in sevens, nothing will be left;

And my basket can contain not more than 150 eggs.

**Question:** How many eggs did the trader have?

*We recommend a time of 20 minutes for solving the puzzle*.

By our experience, we say that if you have taken more than 30 minutes on the puzzle and still don't know how to solve the puzzle, chances are, you are moving around randomly.

Fact is, knowing the answer is not enough—you must be satisfied about the method by which you have found out the answer.

The **method of solution is the more important component**—it might be random or systematic step by step. Again, even when the problem solving method is systematic, it might take a few quick steps to the solution or might be a lengthier series of steps. That's why we devoted time on more than way to solve this puzzle. If you are curious, go on and enjoy the different types of approaches to reach one same destination.

But before going ahead, let's tell you the answer right now—it is 119.

*After the two solution approaches, we didn't stop, but went on to extend the puzzle, even created new puzzles for you and finally formed a framework or problem model for this type of puzzles.*

#### First approach to solve Euclid's division lemma puzzle: by overall Pattern identification, LCM, and Mathematical reasoning

We mark early that the result of division by 7 is not like the other five divisions. In the other five divisions by 2, 3, 4, 5 and 6 we identify the **crucial common pattern** that,

In each case, if we add 1 to the number being divided, the remainder becomes equal to the divisor. In other words

adding 1 to the desired number makes each of 2, 3, 4, 5 and 6 a factor of the number.

Based on this pattern we form the **binding condition that must be satisfied by the solution**, rather any solution to the puzzle if we remove the limiting condition of maximum capacity 150,

A number.1 less than a multiple of LCM 60of 2, 3, 4, 5 and 6, and also divisible by 7 will satisfy all six division conditions

**Trials:** Trying the first multiple 60 less 1, target number 59 is found to be not divisible by 7, but the second multiple of 60, that is, 120 less 1, and target number **119 is divisible by 7 and thus satisfies all given conditions.**

**So answer is****—**119 was the number of eggs in the basket of the trader.

In this approach we have not written any equation, but just used the underlying **division and factor concepts** in our mathematical reasoning.

In the second approach to the solution now, we will use the **mathematical approach with equations.**

#### Second approach to solve Euclid's division lemma puzzle: by division lemma equations, identification of pattern, LCM and trial

In this approach to solve, we write down the equations for five division by 2, 3, 4, 5 and 6 assuming suitable symbols for quotients, and the desired number as $n$,

$n=2q_2+1$;

$n=3q_3+2$;

$n=4q_4+3$;

$n=5q_5+4$, and

$n=6q_6+5$.

If we add $1$ to $n$, **for all five cases** the **remainder becomes equal to the divisor** so that the divisor can be considered as a factor of $(n+1)$.

Thus $(n+1)$ must be a multiple of the LCM of 2, 3, 4, 5 and 6, that is, 60.

Trying and failing with first multiple 60, success is achieved with second multiple of 60, that is 120. Reducing 120 by 1 we find 119 to be divisible by 7 in addition.

**Go through each of the solutions and compare.**

We will now extend the puzzle by **modifying one single condition in the original puzzle**. We will modify the limit of 150 eggs to "more than 200 and less than 900". If you are still curious you will see **how further exploration reveals new patterns**.

### Euclid's division lemma puzzle extended

The extended puzzle statement in brief is as follows,

A trader selling eggs in a village had a quarrel with a man who pulled down the egg basket breaking all the eggs. The trader appealed to the Panchayat for compensation from the offender. When the Panchayat asked the trader how many eggs were broken, the trader replied,

If counted in pairs, one will be left;

If counted in threes, two will be left;

If counted in fours, three will be left;

If counted in fives, four will be left;

If counted in sixes, five will be left;

If counted in sevens, nothing will be left;

And my basket can contain **more than 200 but less than 900 eggs.**

**Question:** How many eggs did the trader have?

In the extended puzzle **the limit of 150 eggs in the basket is changed to a new limiting range of more than 200 but less than 900**. Effectively **we wanted to find the nature of second and subsequent numbers satisfying the same given conditions**, the first being 119.

Give this second puzzle some time before going ahead. **You will surely enjoy to find the way to the solution yourself.**

#### Solution to Euclid's division lemma puzzle extended: by LCM multiple analysis and remainder analysis for 7, identifying a second pattern

We choose the first approach that we have used for solving the original puzzle.

The statement that is **independent of any limiting capacity of the basket, but still satisfies all the other six division conditions** is,

The desired number must be a multiple of 60, the LCM of 2, 3, 4, 5 and 6, less 1 and also divisible by 7.

Let us start from second multiple of 60, that is, 120 as the starting point.

$120-1=119$, when divided by 7 remainder is 0.

For the 3rd multiple of 60 less 1, $180-1=179$ when divided by 7 remainder is 4. This is expected as every additional 60 adds 4 to the remainder when divided by 7,

$60-7\times{8}=60-56=4$.

For the 4th multiple of 60 minus 1, remainder will thus be, $4+4-7=1$, (every 60 adds 4 to the remainder and when it exceeds 7, the excess becomes the remainder; this is modulo 7 operation).

For the 5th multiple of 60 minus 1, remainder will be, $1+4=5$, for 6th multiple of 60 minus 1, remainder is $5+4-7=2$, for 7th multiple of 60 minus 1, remainder is $2+4=6$, for 8th multiple of 60 minus 1, remainder is $6+4-7=3$, and for 9th multiple of 60 minus 1, remainder will be, $3+4-7=0$. At last following the pattern of remainders, 0, 4, 1, 5, 2, 6, 3, the remainder again returns to 0 for 9th multiple of 60 minus 1, that is, 539.

539 is then the second number after 119 satisfying the given six division conditions.

Also, 0, 4, 1, 5, 2, 6, 3 and then 0 is the

repeating pattern of remainders, when consecutive multiples of 60 less 1 are divided by 7.

Now we can easily answer the question, what is the third such number? **It will be distant from the second by 7 numbers of multiple of 60**, that is, it will be,

$9+7=16$th multiple of 60 minus 1, that is, 959 which is greater than 900.

Desired **answer in this case is then 539**.

Seems difficult? It might feel so, but isn't it interesting to discover **a general pattern and predict all possible such numbers** satisfying the given six division conditions?

If you feel still more curious and explorative, you may even form what we call **a framework for any new puzzle of this type**. Well, exploration has its own attractions!

### New puzzles based on Euclid's division lemma

We are now in a position to form new puzzles of this type based on Euclid's division lemma.

#### First new puzzle on Euclid's division lemma

What is the number larger than 40 and smaller than 100, which when divided by 2, 3, and 4, remainder will be one, two and three respectively, and will be divisible by 5?

If you have followed the reasoning till now, you should be able to solve this smaller problem easily within 3 minutes. Give it a try.

#### Solution to first new puzzle on Euclid's division lemma: Pattern identification and rule formation

By the experience we have gained till now we can identify the crucial binding condition easily.

The desired number will be a multiple of LCM 12 of 2, 3, and 4 less 1 and divisible by 5.

This is the *rule that determines every such number without any constraining limits*. This **rule helps us to create the method** to find the solution to the given problem.

#### Solution to the first new puzzle on Euclid's division lemma: Method creation, solution and remainder pattern identification

First multiple of 12 less 1: 11 not divisible by 5: remainder 1: **every 12 when divided by 5 will add 2 to this remainder**.

Second multiple of 12 less 1: 23 not divisible by 5: remainder 3 (1+2=3).

Third multiple of 12 less 1: 35 **divisible by 5 but less than 40** (remainder 3+2=5 minus 5=0. modulo 5).

Fourth multiple of 12 less 1: 47 not divisible by 5: remainder 2 (0+2=2).

Fifth multiple of 12 less 1: 59 not divisible by 5: remainder 4 (2+2=4).

Sixth multiple of 12 less 1: 71 not divisible by 5: remainder 1 (4+2=6 minus 5=1, modulo 5).

Seventh multiple of 12 less 1: 83 not divisible by 5: remainder 3 (1+2=3, the next one will be the answer).

Eighth multiple of 12 less 1: 95 divisible by 5: remainder 0 (3+2=5 minus 5=0, modulo 5).

**95 is the desired number satisfying all conditions.**

The repeating remainder pattern is, 0, 2, 4, 1, 3 and then again 0, and two such numbers will be separated by 5 multiples of 12, that is 60.

The third such number will then be simply, 95 + 60 = 155.

#### Second new puzzle on Euclid's division lemma

What is the first number which when divided by 2, 3 and 4 remainder will be 1, 2 and 3 respectively and will be divisible by 6?

Try to solve this puzzle to gain a new insight into the nature of this types of puzzles.

#### Solution to the second new puzzle based on Euclid's division lemma

As before we form the binding condition for the solution,

The number must be a multiple of LCM 12 of 2, 3, and 4, less 1 and also divisible by 6.

It is easy to see that a multiple of 12 less 1 will never be divisible by 6. So the answer is, **no such number exists**.

Why does this happen?

**The answer lies in the relationship between the last divisor which is a factor with remainder 0 and the other divisors each with remainder 1 less than itself,**

The first set of divisors 2, 3, 4 has factors common to the last divisor 6, and so the multiple of LCM 12 of 2, 3, and 4 less 1 cannot have 6 as a factor.

This insight helps us to form the **binding condition for a valid division lemma puzzle of similar nature**,

The divisor with 0 remainder cannot have any common factor with the set of other divisors.

We are now in a position to form a framework or problem model for similar puzzles based on division lemma.

### Specification or problem model for similar puzzles based on Euclid's division lemma

A *valid similar puzzle based on Euclid's division lemma* must have,

A set of integers as divisors to a number with each division resulting in remainder 1 less than the divisor, and another lone integer as a factor to the same number but having no common factor with rest of the divisors.

With this specification in place let us state the **third new puzzle** for you to solve.

We assure you that we will close this session with this last puzzle.

Try it.

### Third new puzzle on Euclid's division lemma

What is the first number which when divided by 2, 3, 4, 5, and 6 remainder will be 1, 2, 3, 4, and 5 respectively and the number will be divisible by 11?

Do give it a try. It should not be difficult for you now.

#### Solution to the third new puzzle based on Euclid's division lemma

As before the desired number will be a multiple of 60 less 1 and divisible by 11.

Every additional 60 when divided by 11 will add to the remainder 5 or excess to 11 after adding 5 to the remainder.

The repeating remainder pattern will then be, 0, 5, 10, 4, 9, 3, 8, 2, 7, 1, 6 and then 0.

**Two consecutive solutions will be separated by 11 multiples of 60**, that is 660.

The 1st multiple of 60 less 1 results in remainder 4 which is 8 multiples of 60 behind from next remainder 0 in the repeating remainder sequence.

So, $1+8=9$th multiple of 60 less 1, that is **539 will be the first number satisfying all given puzzle conditions. The second such number will be the 20th multiple of 60 less 1, that is 1199, and so on.**

**There will be infinite number of such integers satisfying the given six division conditions.**

#### End note

The specification by no means is a complete one as we have included the phrase "similar puzzle" in every case. There can be varieties of other puzzles using the basic concepts of division, remainder and factors.

### Puzzles you may enjoy

#### Mathematical puzzles

**Reverse cheque puzzle solution**

**Counting eggs puzzles based on Euclid's division lemma**

**Monkey and the coconuts puzzle with solutions**

#### Logic analysis puzzles

**Method based solution to Einstein's logic analysis puzzle, whose fish**

**How to solve Einstein's puzzle whose fish confidently, improved method based solution**

**Logic puzzle, When is Cheryl's birthday**

#### Matchstick puzzles

**Solution to 6 triangles to 5 triangles in 2 moves, first matchstick puzzle**

**Matchstick puzzle 5 squares to 4 squares in 2 moves**

**Matchstick puzzle 5 squares to 4 squares in 3 moves**

**Matchstick puzzle, Turn around the fish in 3 moves**

**Fifth Matchstick puzzle, Move 3 sticks in tic-tac-toe figure to form 3 perfect squares**

**Hexagonal wheel to 3 triangles by removing 4 sticks**

**Convert 5 squares to 4 squares in 3 stick moves, third 5 square matchstick puzzle**

**Matchstick Puzzle - Make the kite nose-dive in 5 stick moves**

**Make 5 squares from 6 in 2 stick moves - 6 square matchstick puzzle**

**Move 3 sticks and convert 5 squares to 4 squares in 4th 5 square matchstick puzzle**

**Move 3 sticks and convert 4 squares to 3 squares matchstick puzzle**

**Move 8 sticks and convert 5 squares to 2 squares matchstick puzzle**

**First Move 3 sticks and make 2 squares matchstick puzzle**

**Second Move 3 sticks and make 2 squares matchstick puzzle**