Euclid’s Division Lemma states that for any two positive integers \(a\) and \(b\), there exists a unique relation \(a=bq+r\), where \(q\) and \(r\) are unique integers. 

Lemma is the proven statement, which is used to verify other mathematical sentences. Euclid’s division lemma is the proven statement that is used in the division of integers. In this article, we will learn everything about the famous Euclid’s lemma for division. Scroll down to learn more!

Euclid’s Division Lemma: Overview

Euclid, the most prominent mathematician, is best known for his work “The elements”. Euclid is known as the father of geometry.

Euclid’s division algorithm suggests a method that deals with the divisibility of integers. In simple words, it says any positive integer a can be divided by another positive integer \(b\) in such a way that the remainder \(r\) obtained is smaller than \(b\).

Euclid division lemma is used to find the HCF of two numbers.

Definition of Euclid’s Division Lemma

Lemma is the proven statement, which is used to verify other mathematical sentences. Euclid’s division lemma is used to find the properties of numbers, such as integers. Euclid’s division lemma states that for any two positive integers \(a\) and \(b\) \((a>b)\), there exists a unique relation \(a=bq+r\), where \(q\) and \(r\) are integers. 

\(a = bq + r,0 \le r < b\)

Here, the integers \(q\) and \(r\) are unique integers and called as quotient and remainder.

The basic concept of Euclid’s division algorithm is Euclid’s division lemma. Euclid’s division lemma is used to divide the two positive integers. 

Division of Numbers

A division algorithm is an algorithm used to find the quotient and/or remainder resulting from the Euclidean division when two integers are given. 

The division algorithm of two numbers is given below:

\({\rm{Dividend = Divisor \times Quotient + Remainder}}\)

Example:
If a number \(48\) is divided by \(5\), then the quotient and remainder obtained are given below:

Here, the number \(9\) is the quotient, and \(3\) is the remainder.

HCF of Numbers

The HCF (Highest Common Factor) of two or more numbers is the highest number of all the common factors of the given numbers. In simple words, the highest common factor of two numbers \(x\) and \(y\) is the largest number that divides both \(x\) and \(y\).

The highest number which divides the given numbers exactly is called the highest common factor. There are different methods of finding the HCF of numbers, such as prime factorisation method, long division method etc., which we have learnt in earlier classes.

The HCF of numbers can be found using Euclid’s division lemma apart from the method mentioned above.

Example:
HCF of \(12576\) and \(4052\) is calculated using both the long division method and Euclid division lemma, as shown in the figure below.

From the above methods, we can say that the HCF of \(12576\) and \(4052\) is \(4\).

Applications of Euclid’s Division Lemma

Below we have provided some of the applications of Euclid’s Division Lemma:

1. Euclid’s division lemma is used to divide the integers.
2. Euclid’s division lemma is the key concept of Euclid’s division algorithm
3. Euclid’s division lemma is used to find the HCF of numbers
4. Euclid’s division lemma is used to find properties of numbers such as even numbers, odd numbers, square numbers, cube numbers, etc.

HCF of Numbers by Using Euclid’s Division Lemma

Euclid’s division lemma states that for any two positive integers \(a\) and \(b\), there exists a unique relation \(a=bq+r\), where \(q\) and \(r\) are integers. 

\(a=b q+r, 0 \leq r<b\)

To calculate the HCF of two positive integers, say \(a\) and \(b\), with \(a>b\), follow the below mentioned steps:

Step-1: Apply Euclid’s division lemma to \(a\) and \(b\) and obtain whole numbers \({q_1}\) and \({r_1}\), such that \(a = b{q_1} + {r_1},0 < {r_1} < b\)

Step-2: If \({r_1} = 0,b\), is the HCF of \(a\) and \(b\).

Step-3: If \({r_1} \ne 0\), apply Euclid’s division lemma to \(b\) and  \({r_1}\) obtain two whole numbers \({q_2}\) and \({r_2}\) such that \(b = {q_2}{r_1} + {r_2}\)

Step-4: If \({r_2} = 0\), then \({q_2}\) is the HCF of \(a\) and \(b\).

Step-5: If \({r_2} \ne 0\), then apply Euclid’s division lemma to \({q_2}\) and \({r_2}\) and continue the above process till the remainder \({r_n}\)  Zero. 

The divisor at this stage i.e. \({r_{n – 1}}\)is the HCF of \(a\) and \(b\).

Example: 
HCF of \(420\) and \(272\) by using Euclid’s division lemma is given below:

Here, \(420>272\). Write the statements as shown below using Euclid’s division lemma.

Here, \(4\) is the maximum number that can give the remainder zero. So, 4 is the HCF of given numbers.

Attempt Mock Tests

Finding Properties of Numbers by Euclid’s Division Lemma

Euclid’s division lemma states that for any two positive integers \(a\) and \(b\), there exists a unique relation \(a=bq+r\), where \(q\) and \(r\) are integers.

We can prove that an even number is in the form of \(2q\) and an odd number is in the form of \(2q+1\) by using Euclid’s division lemma as follows:

Solution: Let us assume a is a positive integer and \(b=2\). By using Euclid’s division lemma, we can write \(a=2q+r\).
Here, \(r=0\) and \(1\) by using the rule \(0≤r<b\)

Case-1: \(r=0\)

Then, by using Euclid division lemma, \(a=2q+0\)
\( \Rightarrow a = 2q,\), where \(q\) is any integer.
Thus, \(2q\) is an even number

Case -2: \(r=1\)

Then, by using Euclid division lemma, \(a=2q+1\), where \(q\) is an integer.
Thus, \(2q+1\) is an odd number.
Thus, we can find that even numbers are in the form of \(2q\), and odd numbers are in the form of \(2q+1\) by using Euclid division lemma.

Solved Examples on Euclid’s Division Lemma

Q.1. Ramu empties the water from two water tanks of \(420\) litres and \(130\) litres by using the mug. What is the maximum capacity of the mug he should use so that no water remains in the tanks?
Ans: The storage of given water tanks is \(420\) litres and \(130\) litres, respectively.
Let \(a=420\) and \(b=130\)
By using Euclid division lemma, \(a=bq+r\)

To find the maximum capacity of the mug, we need to find the HCF of \((420, 130)\)
\(420=130×3+30\)
Here, \(30≠0\), apply Euclid division lemma to the numbers \(130, 30\)
\(130=30×4+10\)
Here, \(10≠0\), apply Euclid division lemma to the numbers \(30, 10\)
\(30=10×3+0\)
Here, the HCF is \(10\).
Hence, the maximum capacity of the mug is \(10\) litres.

Q.2. Use Euclid’s algorithm to find the HCF of the given numbers \(65\) and \(117\).
Ans: Let \(a=117\) and \(b=65\)
By using Euclid’s division lemma to \(117\) and \(65\) to get
\(117=65×1+52\)
Here, \(52≠0\), apply Euclid division lemma to the numbers  \(65, 52\)
\(65=52×1+13\)
Here, \(13≠0\), apply Euclid division lemma to the numbers \(52, 13\)
\(52=13×4+0\)
Therefore, the HCF of \(117\) and \(52\) is \(13\).

Q.3. Army contingent of \(616\) members march behind an army band of \(32\) members in a parade. Now, a couple of groups are said to march in a similar number of columns. What is the maximum number of columns in which they can march?
Ans: To find the maximum number of columns, we need to find the HCF of \(616\) and \(32\).
We apply Euclid’s division lemma to \(616\) and \(32\)
\(616=32×19+8\)
Here. \(8≠0\), apply Euclid division lemma to \(32, 8\)
\(32=8×4+0\)
Therefore, the HCF of \(616\) and \(32\) is \(8\).
Hence, the maximum number of columns in which the people can march is \(8\).

Q.4. A fruit seller has \(420\) mangoes and \(130\) apples. He wants to stack them so that each stack has the same number, and they cover the minor area of the tray. What is the number of fruits that can be placed in each stack to cover the least area of the tray?
Ans: The area of the tray used up in stacking the fruit will be the least if the fruit seller stacks the maximum number of fruits in each stack. 
Since each stack must have the same number of fruits, the number of stacks will be equal to the HCF of \(420\) and \(130\).
To find the HCF of \(420\) and \(130\),
By using Euclid’s division lemma to \(420\) and \(130\)
\(420=130×3+30 \)
Here, \(130≠0\), now consider the divisor \(130\) and the remainder \(30\) and apply Euclid division lemma we get
\(130=30×4+10\) 
Here, \(10≠0\), consider now divisor \(30\) and the remainder \(10\) and apply Euclid division lemma, we get
\(30=3×10+0\)
Here, the remainder obtained is zero. 
Therefore, \(10\) is the HCF of \(420\) and \(130\).
Hence, the fruit seller can make stacks of \(10\) fruits of each kind to cover the least area of the tray.

Q.5. Show any positive odd integer is of the form \(4q + 1\) or \(4q + 3\), where \(q\) is some integer. 
Ans: Consider a, where a is a positive odd integer. Let us take \(b=4\)
We apply the division algorithm with \(a\) and \(b = 4\), and it is given as \(a=4q+r\)
Since \(0 ≤ r < 4\), the possible remainders are \(0, 1, 2\) and \(3\). 
Case-1: When \(r=0\)
\(a = 4q + 0 = 4q = 2(2q) = 2k\) where, \(k=2q\) is any integer.
So, the number \(4q\) is an even number.
Case-2: When \(r=1\)
\(a=4q+1\)
So, the above number is odd.
Case-3: When \(r=2\)
\(a = 4q + 2 = 2(2q + 1) = 2k\), where, \(k=2q+1\) is any integer.
So, the number \(4q+2\) is an even number.
Case-4: When \(r=3\)
\(a=4q+3\)
So, the above number is odd.
Therefore, any odd integer is of form \(4q + 1\) or \(4q + 3\).

Summary

In this article, we have studied the introduction and definition of Euclid’s division lemma. We also studied Euclid’s division algorithm. Euclid’s Division Lemma is the proven statement, that is used in the division of integers. Euclid’s division lemma is used to find the HCF of numbers. It is also important to note that, Lemma is also helpful in finding properties of numbers such as cube numbers, square numbers, even and odd numbers, etc. We discussed the various uses of Euclid’s division lemma, such as finding the HCF of numbers using Euclid’s division lemma and discussing the properties of even and odd numbers.

Hope you find this detailed article on Euclid’s division lemma helpful. If you have any doubts or queries regarding this topic, feel to ask us in the comment section. Stay tuned to embibe.com for more such informative articles. Happy learning!