Euclid Division Lemma

Euclid Division Algorithm

Euclid was the first Greek mathematician who initiated a new way to study Geometry. He is well known for his elements of Geometry. He also made important contributions to the number theory, and one of them is Euclid’s Lemma.


A Lemma is a proven statement that is used to prove other statements.

Euclid’s division algorithm is based on Euclid’s Lemma. For many years we were using a long division process, but this lemma is a restatement for it.

State Euclid’s Division Lemma

Consider a and b be any two positive integers, unique integers q and r such that

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


If b|a, then r = 0. Otherwise, r satisfies the stronger inequality 0 < r < b

Euclid Division Lemma Definition

Theorem: Let a and b be any two positive integers then, there exist unique integers q and r such that

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

If b|a, then r = 0. Otherwise, r satisfies the stronger inequality 0 <= r < b

Proof:

Step 1: 

Let us consider an Arithmetic Progression

………, a-3b, a - 2b, a - b, a, a + b, a + 2b, a + 3b…….

Here the common difference is b and it extends in both directions.

Step 2:

Let r is the smallest non-negative term of the arithmetic progression. Then there exists a non- negative integer q such that 

a - bq = r

a  = bq + r

Step 3: 

As, r is the smallest non-negative integer satisfying the above result.

Therefore, 0<= r < b 

Thus, we have 

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


Euclid’s Division Algorithm:

If ‘a’ and ‘b’ are positive integers such that a = bq + r, then every common divisor of ‘a’ and ‘b’, is a common divisor of ‘b’ and ‘r’ and vice versa.

Dividend = ( Divisor x Quotient ) + Remainder 


Using Euclid’s Division Algorithm for Finding HCF.

Consider positive integers 418  and 33

Step 1: 

Taking a bigger number 418 as a and smaller number 33 as b

Express the numbers in the form a = bq + r

418 = 33 x 12 +22

Step 2:

Now taking the divisor 33 as a and 22 as b apply Euclid’s Division algorithm to get,

33 = 22 x 1 + 11

Step 3:

Again take 22 as new divisor a and 11 as b apply Euclid’s Division Algorithm to get

22 = 11 x 2 + 0

Step 4:

Since, the remainder = 0 so we cannot proceed further.


Step 5:

The last divisor is 11 and we say H.C.F. of 418 and 33 is 11.


Euclid’s Lemma:

Euclid Lemma is a theory proposed by Euclid. Euclid lemma is a proven statement used to prove other statements.


Solved Examples:

Example 1: To find HCF of 210 and 55 using Euclid’s division algorithm.

Solution: Given integers are 210 and 55. 

210>55

Applying Euclid’s division lemma to 210 and 55 we get,

210 = 55 x 3 + 45………………..(i) 

Since the remainder 45 is not equal to zero we apply the division lemma to the divisor 55 and remainder 45 to get,

55 =45 x 1 + 10………………….(ii)

Now, we apply division lemma to the new divisor 45 and new remainder 10 to get


45 = 10 x 4 + 5…………………….(iii)
We now consider the new divisor 10 and the new remainder 5 and apply division lemma to get

10 = 5 x 2 + 0

The remainder at this stage is 0. So the divisor at this stage or the remainder at the previous step is 5

So HCF of 210 and 55 is 5


Example 2: Using Euclid’s Division  Algorithm, find the H.C.F of  135 and 225

Solution: Given integers are 135 and 225

225>135

Applying Euclid’s division lemma, we get

225 = 135 x 1 + 90

Now taking divisor 135 and remainder 90, we get 

135 = 90 x1 + 45

Further taking divisor 90 and remainder 45, we get 

90 = 45 x 2 + 0

Now at this stage remainder is 0 so we get 45 as the H.C.F


Quiz Time:

1.Using Euclid’s division algorithm, find the H.C.F of 196 and 38220.

2.Using Euclid division algorithm find the H.C.F of 441 and 567 


FAQ (Frequently Asked Questions)

1.What is Euclid Division Lemma?

The process of dividing one integer by another, in such a way that it produces a question, a remainder which is smaller than the divisor. The question and remainder are unique under some conditions. 


The basis of the Euclid Division Algorithm is Euclids Division Lemma. We can calculate the highest common factor of two integers using Euclid’s Division Algorithm. 

Definition:- Euclid’s Division Lemma states that if two positive integers a and b, then there exist two unique integers q and r such that a=bq+r where 0 <= r <= b.

2. What is the difference between the Euclid Division Lemma and Euclid Division Algorithm?  

The word Lemma is already a proven statement used to prove other statements, whereas the algorithm is the well-defined steps used to solve the problem.


We use the Euclid Division Lemma to prove other theorems while Euclid Division Algorithm is used to find the Highest common factor of two positive integers where we apply the Euclid Division Lemma.