NCERT Maths Ch 1 Euclid's division lemma puzzle solved by innovative math problem solving techniques
The long-division method masks the complexities, providing you a straightforward, step-by-step solution to Euclid’s division lemma puzzle of counting eggs.
Develop a firm grasp of the seemingly uncomplicated concepts behind Euclid’s division lemma and learn how to use this foundational idea to solve highly intricate problems.
You will also learn innovative problem-solving techniques used in more than one puzzle solutions as a bonus.
The Sections are:
- What are real numbers.
- Euclid's division lemma.
- Why method of long division works.
- Euclid's division lemma puzzle.
- Euclid's division lemma puzzle solution 1.
- Euclid's division lemma puzzle Solution 2.
- Euclid's division lemma puzzle Solution 3.
- Euclid's division lemma puzzle in general form and its solution.
To jump to any of these sections, just click on a link above. To return to previous state, use browser backward navigation button.
The main highlight of this whole session is,
Four different solutions to the Euclid's division lemma puzzle and its general form that will show the power of mathematical reasoning based on the concepts rather than formulas.
What are real numbers
From a practical point of view we define,
Real numbers as the numbers that can be used for measurements of physical quantities in real world. Examples of such quantities are length, weight, time, money, energy and so on.
Number line
The number line is the simplest form of representing all real numbers. The abstract number '0' is placed just at the mid-point of the line (if such a mid-point can be imagined), the positive real numbers occupy their positions on the right side of the center point, increasing indefinitely. In the same way, as a mirror image of the positive real numbers, the negative real numbers occupy equivalent positions on the left of the center point of '0' decreasing indefinitely on the left.
In the figure below, three integers 1, 2 and 3 are shown on the number line in positive and negative form.
Between two integers reside the decimal numbers, like 0.3, 1.253, 20.343434......, -2.000234, and so on. These examples of decimal numbers are all rational numbers as each of these, even the repeating unending decimal 20.343434......, can be expressed as a fraction of the form, $\displaystyle\frac{p}{q}$ where $p$ and $q$ are two integers.
We will be interested mostly in rational numbers because the arithmetic operations and number manipulations can be easily carried out on the rational numbers.
In addition to rational numbers, another type of numbers, the irrational numbers also occupy their proper positions on the number line. These are real numbers but with a bit of awkwardness in their nature—an irrational number cannot be expressed as a fraction and has invariably a decimal part with no repeating pattern but extending indefinitely. Examples of irrational numbers are, 1.01001000100001......, $\sqrt{2}$, $\sqrt{131}$ and so on. The last two numbers are called surds. It is easy to represent surds but when evaluated these expand to non-repeating indefinitely extended decimals. As we can't evaluate an irrational number exactly, we can't use them along with rational numbers for real world use.
A Fraction is not a number, but is a representation of number. For example, a fraction $\displaystyle\frac{3}{4}$ may represent a division of 3 by 4 that results in 0.75 if evaluated, but it may also represent a ratio of two quantities of same units. Usually we feel more comfortable in doing our calculations using fractions rather than using their equivalent decimal forms. With fractions, we get hold of an additional set of resources for simplification—the factors in the numerator and denominator.
Let us now go into the focal point of this session—Euclid's division lemma and its accompanying puzzle.
Euclid's division lemma formalizes the steps in long division
When we were taught the long division method, we actually used the results of Euclid's division lemma. He formalized each step of the long division method by 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; also for given values of $a$ and $b$, values of $q$ and $r$ are unique.
The strict relationship between the divisor and the remainder is,
Remainder must be less than the divisor and greater than or equal to 0. In other words, $0 \leq r \lt b$.
Note: We will use integers for this discussion, though the concepts are valid for numbers with decimal parts also. Secondly, it is implicitly assumed that divisor is smaller than dividend so that quotient is not 0, and remainder is not negative.
Example: When we divide a number, say, 13 by 4, we actually find the number of whole 4's in 13, and the left out portion of 13 that is less than 4. The number of 4's in 13 happens to be 3 which is the quotient, and the left out portion is 1, which is the remainder. Mathematically expressed,
$13=4\times{3}+1$
If we divided 12 by 4, the quotient would still have been 3, but the remainder would be 0. In this case we say, 4 divides 12 fully and is a factor of 12. Here starts the concept of factor,
$12=4\times{3}+0$.
In a long division of say, a number 8152 by a second number 14, at every step of division we find one digit of the final quotient, but for that single step, we adhere to the division lemma. Following is the expanded long division of 8152 by 14.
At the first step of division we divided 81 by 14 resulting in quotient 5, the first digit of final quotient, and remainder 11,
$81=14\times{5}+11$.
At the second step of division we divided 115 by 14 resulting in quotient 8, the second digit of final quotient, and remainder 3,
$115=14\times{8}+3$.
At the third and last step of division, we divided 32 by 14 resulting in the quotient 2, the third digit of final quotient, and remainder 4,
$32=14\times{2}+4$.
All digits of the main number 8152 having been used up and remainder 4 being less than the divisor 14, we stop at this third step to say that the final quotient is 582 with final remainder as 4.
Why method of long division works
In long division method, the dividend 8152 is implicitly broken up into three parts,
$8152=8100+50+2$
If you look closely you will find that effectively at the first step you have divided 8100 by 14 resulting in quotient of 500 and remainder 1100,
$8100=14\times{500}+1100$.
At the second step thus the dividend is transformed in broken up form to,
$1152=1150+2$.
Thus in the second step, dividing 1150 by 14 results in a quotient of 80 and remainder 30,
$1150=14\times{80}+30$.
The long-division quotient increases to $500+80=580$ and the dividend is transformed to 32—we have reached the unit's stage and do not need to break it up further,
$32=14\times{2}+4$.
This is the third and last stage of the long-division resulting in final quotient, $580+2=582$ and final remainder, $4$.
At each step, the division satisfies the taken-for-granted Euclid's division lemma, and you never had to worry about the above complexity. The brilliant long-division method hides the complexities and presents you with a simple straightforward step by step method.
We will now take up the old classic puzzle that highlights the depths of Euclid's division lemma.
Euclid's division lemma puzzle
This is a folk puzzle that is based on the Euclid's division lemma.
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?
This is a rich puzzle relevant to the topic and you should try to solve the puzzle giving it some time. Just remember, finding the answer is not enough, you have to justify how you arrived at the answer.
Euclid's division lemma puzzle solution 1: by Mathematical reasoning and remainder analysis involving 6 and 7
We are used to solving puzzles by analyzing the problem description, finding useful insight into the nature of the problem and solving the puzzle all in mind. This generally produces the solution quickly.
Taking this approach we observe that only 7 is the odd man out as its division results in a remainder 0, but not 6 according to the pattern followed in the other cases. For all the other divisors 2, 3, 4, 5 and 6 the remainders are 1, 2, 3, 4 and 5 respectively, less than the divisor by just 1.
Recognizing this specialty of 7, we choose to analyze the behavior of the remainders for 7 and its closest neighbor 6. This we call remainder analysis.
For $1\times{7}$, dividing by 6 gives remainder 1;
For $2\times{7}$, dividing by 6 gives remainder 2;
For $3\times{7}$, dividing by 6 gives remainder 3, and so on till,
For $5\times{7}$, dividing by 6 gives remainder 5, and
For $6\times{7}$, both 7 and 6 become two factors fully dividing the number. Each 7 added 1 to the remainder when divided by 6.
So we know now,
If we subtract 7 from 42, the result 35 will give 5 as remainder when divided by 6 but will be fully divisible by 7. This is the pattern that should identify the answer.
The answer to the puzzle must then be a multiple of 42 less by 7, and that satisfies all given conditions. This is the crucial pattern in this solution approach.
For first multiple of 42 less 7, that is 35, division by 5 results in remainder 0 and violates the condition of remainder 4. So 35 cannot be the answer.
If we try the next multiple of 42 less 7,
$2\times{42}-7=77$, again division by 5 does not produce remainder 4.
But in the third attempt on the third multiple of 42 less 7,
$3\times{42}-7=119$, we get the answer as it satisfies all given conditions.
We have used minimum number of given resources to identify a crucial pattern and method to arrive at the answer.
Euclid's division lemma puzzle solution 2: by overall Pattern identification, LCM, and Mathematical reasoning
Instead of focusing on 7, the odd number that behaves not like the other divisors, we turn our attention to the other five divisors 2, 3, 4, 5 and 6 and identify the crucial overall 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.
So, a number 1 less than a multiple of LCM 60 of 2, 3, 4, 5 and 6, and also is divisible by 7, will be the answer.
Trying the first multiple 60, target number 59 is found to be not divisible by 7, but the second multiple of 60, that is, 120 less 1, which is 119, is divisible by 7 and thus satisfies all given conditions.
Euclid's division lemma puzzle solution 3: by division lemma expressions, identification of pattern, LCM and trial
In this solution we write down the five division relations 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 less 1, success is achieved with second multiple of 60, that is 120 less 1, which is 119 and, which in addition is divisible by 7.
Go through each of the solutions and compare.
We call this approach of solving a problem in more than one way as Many ways technique. If you practice this, ability to discover new possibilities in a given situation increases.
We will now extend the puzzle by modifying one single condition in the original puzzle. If you are still curious you will see how further exploration reveals new patterns.
Euclid's division lemma puzzle in general form
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.
Solution to Euclid's division lemma puzzle extended: by LCM multiple analysis and remainder analysis for 7, identifying a second pattern
We choose the second 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 third multiple of 60 less 1, $180-1=179$ when divided by 7 remainder is 4. This is expected as every 60 adds 4 to the remainder when divided by 7.
For fourth 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 operation).
For 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 numbers of division conditions.
Also, 0, 4, 1, 5, 2, 6, 3 and then 0 is the repeating pattern of remainders, when 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 (which is the number of members in the repeating sequence of remainders) numbers of multiple of 60, that is, it will be,
$9+7=16$th multiple of 60 minus 1, that is, 959.
As 959 is beyond the upper limit of 900, desired answer in this case is, 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 numbers of division conditions?
If you feel still more curious and inquisitive about the power of Euclid's division lemma, you may look into the solution of famous and least solved Monkey and Coconuts puzzle.
Read the other NCERT Class 10 Chapter 1 solutions and refer to the full list of NCERT Class 10 Math solutions.