## Euclid's division algorithm for HCF, division lemma and problem solutions

In the* first part of NCERT solutions for class 10 maths on Real Numbers*, we introduced

*basic concepts on real numbers*, the

*long division method*formalized by Euclid in his

*division lemma*and treated in some details the solutions of a rich classic puzzle

*highlighting the application of division lemma.*

Building on these concepts, we will now introduce Euclid's division algorithm for finding HCF of two integers and proceed to solve a few representative problems.

### Euclid's division algorithm for finding HCF of two integers

From our schooldays we knew this as an ingenious step by step method that can be followed without much thought to find HCF of two integers. The commonly known name of this method has been continuous division method for finding HCF. Formally, this is Euclid's division algorithm and is based on Euclid's division lemma. As the method consists of a precise series of well-defined steps, it is called an algorithm.

The **steps of the division algorithm** to find the HCF between two integers are,

**Step 1.** Divide larger integer $a$ by smaller integer $b$, resulting in remainder $r_1$. The quotient, say $q_1$ is not of interest here. If remainder is 0, $b$ is the HCF of $a$ and $b$. This is easily understandable.

**Step 2.** **Remainder and divisor** in the previous step now **change their roles** to become the divisor and dividend respectively in this present division operation. So, when this step is executed just after step 1, the divisor becomes $r_1$ and dividend $b$, that is, $b$ is divided by $r_1$ in this step.

In general when this step is repeated, the remainder of the present division $r_n$ if zero, $r_n$ is the HCF between $a$ and $b$.

**Step 3.** Step 2 is repeated till remainder is 0 or 1. The integer 1 is not considered as a factor and when the final remainder is 1, it means—the two integers $a$ and $b$ do not have any common factor and hence are **co-prime numbers**.

Observe that the second step is a repetitive one which in algorithmic terms is called a loop.

Let us show an application of the algorithm **to find the HCF of two integers 66 and 420** in the following figure.

**Final result:** HCF of 66 and 420 is 6.

In the first stage, the larger integer 420 is divided by the smaller 66. Quotient 6 is not important, but the remainder 24 is.

In the second stage, the previous stage remainder 24 divides the previous stage divisor 66 which becomes the dividend in this stage. The arrow indicates this **change of role. Remainder is non-zero 18 now.**

In the third stage previous stage remainder 18 divides previous stage divisor 24, resulting in non-zero remainder 6.

In the fourth and last stage previous stage remainder 6 divides previous stage divisor 18 resulting in 0 remainder, and so 6 becomes the HCF of original two integers 66 and 420.

This is a simple to follow step by step method for finding HCF of two integers. When more than two numbers are involved in finding HCF though, it might be faster and easier to follow HCF by factorization. To know more about this method you may refer to our articles, * Factorization* and

*.*

**HCF and LCM**Before going ahead further we will spend some time on why the division algorithm works as it is intended to work. We will discuss underlying mechanism and concept.

#### Mechanism of Euclid's division algorithm

The division algorithm is primarily based on the division lemma as, right from the first stage, the dividend is split up into two parts, the first part containing the product of divisor and quotient and the second part, the remainder. The dividend and the divisor to have a HCF, the HCF must be a factor of the remainder also. It will be easier to understand from the division lemma equation for the first step,

$a=bq_1+r_1$.

Unless $b$ and $r_1$ share a factor, $a$ and $b$ cannot have that factor common to them. Let's assume $F$ to be the HCF between $b$ and $r_1$ so that,

$b=Fb_1$, and

$r_1=Fr_{11}$.

So, $a=F(b_1q_1+r_{11})$.

HCF $F$ is thus a factor of $a$ in addition to $b$ and $r_1$.

This relationship will always be true by the nature of the division and remainder mechanism.

For every subsequent division also this relationship holds. Finally when there is no remainder, the divisor at that stage becomes the HCF of itself and the dividend, and going backwards, finally HCF of original two integers $a$ and $b$ (and first division remainder also).

To further clarify let's jot down the division lemma equations for our example problem.

**First stage:** $420=66\times{6}+24$, all three of 24, 66 and 420 have the HCF 6.

**Second stage:** $66=24\times{2}+18$, all three of 18, 24 and 66 have the HCF 6.

**Third stage:** $24=18\times{1}+6$, all three of 6, 18 and 24 have the HCF 6.

**Last stage:** $18=6\times{3}$, 6 finally reveals itself as the HCF of 6 and 18, hence of 18 and 24, hence of 24 and 66, and lastly then HCF of 66 and 420.

It is a focusing mechanism narrowing down to the HCF hidden in the remainders.

Now let us recap by **summarizing the core concepts involved**. We will build upon more basic concepts to reach higher level concepts and in this process will link them into a **chain of concepts**. This is an important technique in getting insight into all the constituent concepts. *Here our focus is not on formulas or methods but on concepts.*

You may choose to skip the following section to directly go through the problem solutions based on division lemma and division algorithm following it.

### Core concepts based on division of one number by another

#### Breaking up of a number by factorization

When man learned counting and formed place value mechanism to build or count larger and larger (or smaller and smaller in case of decimals) numbers, multiplication and division gained more importance compared to addition and subtraction. You would easily appreciate the reason when you think of the result of the product, $8\times{129}$ as adding 8 to itself 129 times. With just addition, you cannot relate or evaluate large numbers from smaller ones easily, you needed a new operation and accompanying method of multiplication (and division) to easily explore the relations between numbers spreading over as large (or small) range as you want.

To examine large numbers in more depth thus the **concept of factors** is born. With this powerful new concept, you can now break up a number, say 798 into its component factors as,

$798=2\times{3}\times{7}\times{19}$.

And how do you get these component factors from 798? It is by **dividing** 798 systematically by 2, 3 and so on. You have to use the divisibility concepts to carry out factorization.

What happens when you cannot break up a number, say 131, into any smaller number? You realize that you have hit upon a special type of number that cannot be further broken up into factors. This special type of numbers, called as prime numbers, later attained the status of one of the most mysterious types of numbers.

When we factorize, we always attempt to find prime factors.

#### Euclid's division lemma

When you divide an integer by another smaller integer, effectively you take out as many numbers of the smaller integer as possible from the larger number. For example by the division of 12 by 3, you take out 4 numbers of 3 and nothing of 12 remains left. You declare 3 as a factors of 12.

For an integer to be identified as a factor of a larger integer, division of the larger by the smaller leaves remainder 0.

But in a division it is always possible that some non-zero value of the larger number will be left out after taking out the smaller number maximum number of times from the larger number. This is a natural consequence of division. When man started to use division, this possibility obviously occurred. Euclid was reportedly the first to record this natural and general nature of division in his division lemma,

$a=bq+r$,

where $a$ is the larger dividend, $b$ the smaller divisor, $q$ the quotient that tells us how many maximum number of $b$'s are there in $a$ and $r$ is the remainder that can be zero or if not zero, must be less than the divisor $b$ as, by the process of division we have taken out all $b$'s possible.

This general concept of division along with its precise mathematical expression helps to analyze and solve a large number of problems on numbers. It is what we call, **a foundational concept**.

#### Relating two integers by HCF and LCF

As is human nature, when we discover a new concept, we explore further and try to discover new concepts based on the earlier concepts. When the **factors** concept became known, two integers were broken up into their factors, and then the two were related by two new concepts of **HCF and LCM**. These two gave rise to a great many new ways to examine and use various forms of numbers. In their own right HCF and LCM both attained crucial importance and can also be classified as **foundational concepts**.

**Example of HCF and LCM of 66 and 420 in factorized form**

Assuming that we have already factorized 66 and 420, we can write the two numbers in their prime factor component form as,

$66=2\times{3}\times{11}$, and

$420=2\times{2}\times{3}\times{5}\times{7}$.

Examining the two we identify one number of 2 and one number of 3 as the only prime factors common to both 66 and 420, and declare their HCF as,

$2\times{3}=6$.

HCF in general may not be a prime factor but may further be broken up into other prime factors.

Similarly we identify 2, 2, 3, 5, 7 and 11 as the unique set of prime factors among all the factors of 66 and 420 combined together and occurring only once. Product of these factors occurring just once in the combined set we get their LCM as,

$2\times{2}\times{3}\times{5}\times{7}\times{11}=11\times{420}=4620$.

This is the smallest number that can be divided exactly by both 66 and 420.

In this session our focus is on HCF and so the question arises, how to find the HCF of two integers.

Continued division method or **Euclid's division algorithm** provided us with a simple and systematic way to achieve this task.

### Solutions to problems based on division, Euclid's division lemma, factorization, HCF and Euclid's division algorithm

**Problem 1.** Find the HCF of 867 and 255.

The following figure shows finding out HCF 51 of two integers 867 and 255 by Euclid's division algorithm.

**Answer: 51.**

**Problem 2.** Find the HCF of 135 and 225.

How to find the HCF 45 of the two integers 135 and 225 by Euclid's division algorithm is shown below.

**Problem 3.** Find the HCF of 38220 and 196.

How to find the HCF 98 of the two integers 196 and 38220 by Euclid's division algorithm is shown below.

Observe that the quotient for division of 38220 by 196 is of two digits and in the first two steps we evaluated the remainder 196 and the quotient 19 by usual division, switching back to division algorithm only in the third step. This is a mixed method with normal division mixed with division algorithm when a remainder or divisor results in a two or more digit quotient by dividing the dividend at that stage.

**Problem 4.** Show that any positive odd integer is of the form of $6q+1$, $6q+3$, or $6q+5$ where $q$ is any positive integer including 0.

**Solution 4.**

If $q$ is **any positive integer excluding 0**, when **any positive integer** $N$ is divided by $6q$, remainder can be 0, 1, 2, 3, 4 and 5. But as $N$ is not just any positive integer, but also is odd, the remainders 0, 2 and 4 make $N$ an even number and so these remainders are invalid. Following shows how $N$ becomes even, if remainder is say, 2. We will use Euclid's division lemma for the task,

$N=(6q)q_2+2=2(3qq_2+1)$.

It follows then, any positive odd integer $N$ when divided by $6q$, possible and valid remainders are 1, 3 and 5 only. Mathematically it is equivalent to,

$N=6q +r$, where $r$ can be 1, 3 and 5 only.

In other words, any positive odd integer can be expressed in the form of, $6q+1$, $6q+3$ or $6q+5$, and now only we include the value of 0 in the possible set of values of $q$ to cater to the first three positive integer values of $N$, 1, 3 and 5. With $q=1$, we will get the next three odd integer values of $N$, 7, 9 and 11, and so on.

**Problem 5.** An army contingent of 616 members is to march behind an army band of 32 members in a parade. The two groups are to march in same number of columns. What is the maximum number of columns in which they can march?

**Solution 5.**

By the problem description, the number of columns in which the army band moves must be a factor of 616. For example, if the army band moves in two columns, 16 band members form each column of the band, and 308 army members form each column of army contingent. This is the lowest common factor of 32 and 616. To maximize the number of columns then we need to find the highest common factor of 32 and 616. Let us find the HCF by Euclid's division algorithm as shown below.

HCF of 32 and 616 is 8, and so the **answer is, 8 columns.**

**Problem 6.** Use Euclid's division lemma to show that the square of any positive integer is either of the form $3m$ or $3m+1$ for some positive integer $m$.

Lets assume $N$ as the any positive integer square of which is to be expressed in the form of $3m$ or $3m+1$ for some positive integer $m$.

We look at the target expressions $3m$ and $3m+1$ and deduce that our job would be easier if we can express $N$ in the form of an expression. $N=3m+x$. If we could do so, $N^2 =9m^2 + 6mx+x^2$ would have first two terms containing factor 3, a big step towards the solution.

With this possibility in mind, we visualized positive integers in consecutive triplets as below.

We grouped [0 1 2], [3 4 5], [6 7 8], [9 10 11] ...and so on to cover all integers. Each group started with a multiple of 3, say 3n with n as some integer including 0. The second number of the group is thus, 3n+1 and the third 3n+2. The first number of the next triplet is again a multiple of 3.

Thus we know that any positive integer $N$ can be expressed in the form of, $3n$, $3n+1$ or $3n+2$. This follows from the nature of the integers as well as dividing any integer by 3 with remainders 0, 1 or 2. Either way we can arrive at this result, but visualization helps to absorb and memorize a concept better.

In division lemma form we can express the three forms as,

$N=3n$, remainder 0 and N a multiple of 3

$N=3n+1$, remainder 1 when divided by 3, and,

$N=3n+2$, remainder 2 when divided by 3.

For $N=3n$, a multiple of 3, on squaring it the result will still remain a multiple of 3 in the form of say 3m, where m is some integer. This is obvious. We need to work on the other two forms a bit though.

Squaring $N=3n+1$, we get,

$N^2=9n^2+6n+1=3(3n^2+2n)+1=3m+1$ where m is some integer.

Similarly squaring $N=3n+2$ we get,

$N^2=9n^2+12n+4=3(3n^2+4n+1)+1=3m+1$, where m is again some integer.

So any positive integer can be expressed in the form of $3m$ or $3m+1$, where $m$ is some integer.

**Problem 7.** Use Euclid's division lemma to show that the cube of any positive integer is of the form $9m$, $9m+1$, or $9m+8$.

Dividing any positive integer N by 3 we get possible remainders 0, 1 or 2 as shown below in Euclid's division lemma form,

$N=3n$, remainder 0

$N=3n+1$, remainder 1, and

$N=3n+2$, remainder 2.

When we raise $N$ to the power of 3, the first equation becomes, $N^3=27n^3$ conforming to the form, $N=9m$, where m is some integer.

Similarly the cube of second equation becomes,

$N^3=27n^3+27n^2+9n+1=9m+1$, where m is some integer.

Lastly the cube of the third equation becomes,

$N^3=27n^3+54n^2+36n+8=9m+8$, where m is some integer.

Thus cube of any positive integer N can be expressed in the form of $9m$, $9m+1$ or $9m+8$.

Next, we will show you a few more types of word problems based on Euclid's division lemma or division algorithm, with answers and then solutions to give you some idea of the depth of the concepts on division lemma and HCF by division algorithm.

### New problem examples

**New problem 1. **Find the maximum number of students among whom 910 pens and 1001 pencils can be distributed in such a way that each student gets same number of pens or pencils.

**New problem 2.** A milkman has 21 liters of whole milk, 42 liters of toned milk and 63 liters of double toned milk. If he wants to pack the three types of milk in cans so that in no can two types of milk are mixed, then what is the minimum number of cans he would require?

**New problem 3.** Three sets of books on Maths, Science and Social studies have 240, 336 and 96 books in each set respectively. The books need to be stacked in such a way that all the books are stacked subject-wise and number of books in each stack is same. Find the total minimum number of stacks required.

**New problem 4.** Find the least number of square tiles required to pave the floor of a room 15m 17cm long and 9m 2cm broad.

**New problem 5.** Find the largest possible length that can be used for measuring exactly the three lengths, 7m, 3m 85cm and 12m 95cm.

#### Answers to the new problems

**New problem 1:** Answer: 91.

**New problem 2:** Answer: 6.

**New problem 3.** Answer: 14.

**New problem 4:** Answer: 814.

**New problem 5:** Answer: 35 cm.

### Solutions to the new problems

#### Solution to New problem 1.

**New Problem 1:** Find the maximum number of students among whom 910 pens and 1001 pencils can be distributed in such a way that each student gets same number of pens or pencils.

As each student gets same number of pens when the 910 pens are distributed among them, product of number of students and number of pens each student got must be equal to 910. In other words, along with number of pens each student got,

Number of students must also be a factor of 910.

For equal distribution of 1001 pencils also same conclusion is true. Thus we find number of students, by the nature of the problem, must be a common factor of 910 and 1001. The problem demands us to find such highest number of students. The answer will then be simply the HCF of 910 and 1001. Following figure shows the application of Euclid's division algorithm to find the HCF 91.

**Answer:** Maximum number of students will be 91.

#### Solution to new problem 2.

**New Problem 2**: A milkman has 21 liters of whole milk, 42 liters of toned milk and 63 liters of double toned milk. If he wants to pack the three types of milk in cans so that in no can two types of milk are mixed, then what is the minimum number of cans he would require?

First conclusion we make from the problem description is,

Capacity of each can is same and it must be a factor of 21, 42 and 63.

This is because all of the milk has been packed in cans, and no two types of milk are mixed.

Applying deductive reasoning, next conclusion we make is,

Larger the capacity of each can is, smaller the number of cans required will be.

It follows then, for minimum number of cans, the can capacity must be maximum possible factor of 21, 42 and 63.

By observation we can easily say, the HCF of 21, 42 and 63 is 21.

This gives us the minimum number of cans as,

$1 +2 +3=6$.

**Answer:** Minimum number of cans required will be 6.

#### Solution to new problem 3.

**New Problem 3.** Three sets of books on Maths, Science and Social studies have 240, 336 and 96 books in each set respectively. The books need to be stacked in such a way that all the books are stacked subject-wise and number of books in each stack is same. Find the total minimum number of stacks required.

Number of books in each stack is same for each subject, and so this stack size in number of books must be a common factor of 240, 336 and 96.

Secondly, larger the stack size is, smaller the number of stacks will be, and for minimum number of stacks, the stack size must be the maximum possible. HCF of the three numbers, 240, 336 and 96 will have to be found out then.

By Euclid's division algorithm, we can find out the HCF of exactly two integers.

**Question is now:** How to find out HCF of three integers by Euclid's division algorithm?

**The method for finding HCF of three numbers is:** First find HCF of any two suitable numbers, and in the second step find the HCF of the third number and HCF of the first pair of numbers.

Choosing 240 and 336, the HCF of the pair is 48 as shown below,

Now we find 48 to be a factor of 96 and so it is the HCF of the three numbers 240, 336 and 96.

Minimum number of stacks required will then be,

$\displaystyle\frac{240}{48}+\displaystyle\frac{336}{48}+\displaystyle\frac{96}{48}=5+7+2=14$.

**Answer:** 14.

#### Solution to the new problem 4

**New Problem 4.** Find the least number of square tiles required to pave the floor of a room 15m 17cm long and 9m 2cm broad.

**First conclusion: **

To have the least number of tiles, the size of the tiles must be maximum.

**Second conclusion:** Being square tiles area of a tile is $a^2$, where $a$ is its side length. To pave the floor fully then,

Side length of a square tile must be a factor of both length and breadth of the floor.

It follows,

Side length of a tile as HCF of floor length and floor breadth will give us minimum number of tiles required.

Converting the floor length and floor breadth into cm we get HCF of 1517 cm and 902 cm as 41 cm by Euclid's division algorithm as shown in the figure below,

Least number of tiles required will then be,

$\displaystyle\frac{1517}{41}\times{\displaystyle\frac{902}{41}}=37\times{22}=814$.

**Answer:** 814.

The number will be the product because first division gives the number of columns and the second, number of rows.

The figure below for a smaller floor of length 24 m and breadth 16 m with square tile side length 8 m as the HCF of floor length and floor breadth should make the situation clear,

Dividing length 24 m by tile side length 8 m gives number of tiles in each row as 3, and dividing breadth 16 m by tile side length 8 m gives number of tiles in each column as 2. Product of these two numbers 6 gives the total number of square tiles required to cover the floor.

#### Solution to new problem 5.

**New Problem 5.** Find the largest possible length that can be used for measuring exactly the three lengths, 7m, 3m 85cm and 12m 95cm.

The three lengths converted to cm are, 700, 385 and 1295. The largest possible length for measuring these three lengths exactly (with no remainder) would be the HCF of the three numbers.

Choosing the first pair of numbers, 700 and 385, we find the HCF 35 of the two numbers as shown in the figure below,

We find this HCF 35 dividing the third number 1295 exactly (quotient 37) and so is the HCF of the three.

**Answer.** 35 cm.

Related articles on NCERT solutions follow.

### NCERT Solutions for Class 10 Maths

#### Real Numbers

**NCERT Solutions for Class 10 Maths on Real numbers part 2, Euclid’s division algorithms, HCF and problem solutions**

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

#### Introduction to Trigonometry

**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**