## Euclid's division lemma for long division and Solutions to Euclid's division lemma puzzle

Euclid's division lemma and Euclid's division lemma puzzle solutions form main content in this 1st part of NCERT Class 10 maths solutions on real numbers.

We will show three different solutions to the puzzle to highlight the *power of mathematical reasoning based on the concepts rather than formulas.*

**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 reasoningbased 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, you may even form what we call **a framework or domain model for any new puzzle of this type**. Well, exploration has its own attractions!

Related articles on NCERT solutions for class 10 maths follow.

### NCERT Solutions for Class 10 Maths

#### Chapter 1: Real Numbers

**NCERT Solutions for Class 10 Maths on Real numbers part 1, Euclid’s division lemma puzzle solutions**

#### Chapter 2: Polynomials

#### Chapter 3: Linear Equations

**NCERT solutions for class 10 maths Chapter 3 Linear equations 7 Problem Collection**

**NCERT solutions for class 10 maths Chapter 3 Linear equations 6 Reducing non-linear to linear form**

**NCERT solutions for class 10 maths Chapter 3 Linear Equations 4 Algebraic solution by Elimination**

**NCERT solutions for class 10 maths Chapter 3 Linear Equations 3 Algebraic solution by Substitution**

**NCERT solutions for class 10 maths Chapter 3 Linear Equations 2 Graphical solutions**

**NCERT solutions for class 10 maths Chapter 3 Linear Equations 1 Graphical representation.**

#### Chapter 4: Quadratic equations

**NCERT solutions for class 10 maths Chapter 4 Quadratic Equations 1 What are quadratic equations**

**NCERT solutions for class 10 maths Chapter 4 Quadratic Equations 2 Solving by factorization**

**NCERT solutions for class 10 maths Chapter 4 Quadratic Equations 3 Solution by Completing the square**

#### Chapter 6: Triangles

**NCERT solutions for class 10 maths chapter 6 Triangles 1 Similarity of Triangles and Polygons**

**Solutions to Exercise 2 Chapter 6 NCERT X Maths, Characteristics of Similar triangles**

#### Chapter 8: Introduction to Trigonometry, Concepts and solutions to exercise problems

*NCERT solutions for class 10 maths chapter 8 Introduction to Trigonometry 1 Trigonometric Ratios*

*NCERT solutions for class 10 maths chapter 8 Introduction to Trigonometry 4 Trigonometric identities*

#### Chapter 8: Introduction to Trigonometry, only solutions to selected problems

**NCERT Solutions for Class 10 Maths on Trigonometry, solution set 6**

**NCERT Solutions for Class 10 Maths on Trigonometry, solution set 5**

**NCERT Solutions for Class 10 Maths on Trigonometry, solution set 4**

**NCERT Solutions for Class 10 Maths on Trigonometry, solution set 3**

**NCERT Solutions for Class 10 Maths on Trigonometry, solution set 2**

**NCERT Solutions for Class 10 Maths on Trigonometry, solution set 1**