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

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.

 

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