Courses for Kids
Free study material
Offline Centres
Store Icon

Type-1 - Euclid's Division Lemma

Last updated date: 15th Jul 2024
Total views: 684.9k
Views today: 7.84k

Euclid’s Division Lemma and its meaning

According to Euclid’s Division Lemma, any positive integer can be divided by the other, in a manner that leaves a remainder that is smaller than the other integer. This can also be called the long division process. Mathematically, this can be stated as a dividend will be equal to a divisor multiplied by the quotient added with the remainder. The Euclidean division algorithm is the main basis of Euclid’s division lemma. It is used for deriving the HCF (Highest Common Factor), which is the largest number that is divisible by two or more positive integers.

Competitive Exams after 12th Science

Euclid’s Division Lemma Proof

As per Euclid’s Division Lemma, for every two positive integers, say 'a' and 'b', there exists two unique integers say 'q' and 'r', such that a = bq+r, 0 ≤r <b.

Let us understand this through a numerical example-

We can take, a = 9 and b = 1.

9 = (1 × 9) + 0

Here, q = 9 and r = 0, and we can clearly see that 0 ≤ r < 1.

Important Topics Under Euclid's Division Lemma

Serial Number

Topic Name






Highest Common Factor


Euclid's Division Algorithm


Remainder Theorem

Numerical Problem 2:

To find the Highest Common Factor (HCF) of both the numbers 78 and 980. 

Choose the largest integer first, i.e. 980 

We know that as per the Euclid Division Lemma, a = bq + r where 0 ≤ r ≤ b;

980 = 78 × 12 + 44

Now here 

Dividend, a = 980, 

Divisor, b = 78, 

Quotient, q = 12 and 

Remainder, r = 44.

By considering the divisor as 78 and the remainder as 44 and applying the Euclid division method once again, we get

78 = 44 × 1 + 34

Similarly, consider the divisor as 44 and the remainder 34 and apply the Euclid division method again, we get

44 = 34 × 1 + 10

Following the same procedure again, till we reach on o the remainder as Zero

34 = 10 × 3 + 4 (Divisor = 34, Remainder = 10)

10=4×2+2 (Divisor = 10, Remainder = 4)


We got the remainder as 0. Hence we need to stop applying the Euclid division method further. 

From observation of the last value, we can conclude that 2 is the Highest common factor(HCF) of the two given numbers 980 and 78.

FAQs on Type-1 - Euclid's Division Lemma

1. What is the Division Lemma by Euclid?

A lemma refers to a statement that is proven to prove another statement. According to the division lemma by Euclid, for any two given positive integers, say 'a' and 'b', the condition 'a = bq+r ' where 0 ≤ r < b will always hold true. In Mathematics, we can represent the lemma as Dividend = (Divisor × Quotient) + Remainder. For example, for two positive numbers 59 and 7, Euclid's division lemma holds true in the form of 59 = (7 × 8) + 3.

2. What are a few important points to remember about Euclid's division lemma? 

The most important points that you must recall about Euclid's division lemma are listed below: 

On the division of one integer by another integer which is non zero, you are left with two figures. These are the quotient and the remainder.

In every division sum, the remainder will always be less than the divisor. 

One of the main uses of Euclid’s lemma is the calculation of the Highest Common Factor (HCF) for large numbers. Examples include finding HCF of 42 and 62. 

3. What is the formula for Euclid's Division Lemma

The Euclid's division formula is as follows:

a = bq + r, 0 ≤ r < b, 

Here 'a' as well as 'b' represent two integers which are positive 'q’s, as well as ‘r’, are two integers that are unique. These integers are such that it satisfies an equation. The equation is a = bq+r. This can be better understood by an example. For instance, a= 9 and b = 3. 

This is the form of a=bq+r will be 9 = (3×3)+0

Now, here we can see that both q and r are both positive and equal to 3 and zero and that 0 ≤ r < 3.

4. How can we find the HCF with the use of  Euclid's Division Lemma?

One of the main uses of Euclid's Division Lemma is to find the HCF of two large numbers. This can be done by using the following statement where 'a = bq +r', where 0 ≤ r < b. Here both 'a' and 'b' are positive integers and a > b. For finding out the HCF of numbers 'c' and 'd', we will follow the steps listed below. 

First, we will apply the lemma to 'c' and 'd'. We will find whole numbers in the form 'q' and 'r' such that c = dq + r, 0 ≤ r < d. 

If the value of r=0, then the HCF of 'c' and 'd'. If  r ≠ 0, then we will apply the lemma to 'd' and 'r'

Now, repeat this process till the remainder becomes zero. At the step where the remainder is zero, the divisor is the HCF.

5. What is the application of Euclid's Division Lemma?

There are many applications of Euclid's Division Lemma. These are listed below-  

For finding out the properties of numbers. For example, with the use of the lemma we can show that every positive even number is in the form of '2q' whereas every positive odd number is of the form '2q+1.' 

Secondly, it is used while finding out the HCF of two numbers which are very large. For example, we use the lemma while finding out the HCF between 525 and 245.