Euclid’s Division Lemma Class 10th

Introduction

Euclid’s Division Lemma is generally an algorithm that is derived by Greek Mathematician Euclid. This lemma is based on the Division of Real Numbers. We have already studied the division algorithm, in which if we divide a number by another number we get two numbers a quotient and a remainder (sometimes the remainder may be zero). According to the division algorithm

Dividend = Divisor × Quotient + Remainder

Explanation

Let’s understand by some examples

(1) 67 = 4×16 + 3 [Dividend = 67, Divisor = 4, Quotient = 16, Remainder = 3]

(2) 88 = 15×5 + 13[Dividend = 88, Divisor = 15, Quotient = 5, Remainder = 13]

(3) 45 = 9×5 + 0 [Dividend = 45, Divisor = 9, Quotient = 5, Remainder = 0]

With the help of the above examples, we have to keep in mind the rules related to the Division Algorithm.

1) Dividend can be zero but Divisor never can be zero because of an indefinite solution.

2) Remainder is always smaller than Divisor and sometimes it may be zero.

3) Sometimes Quotient can be zero.

Euclid’s Division lemma is based on the Division algorithm and with its help, we can state it as follows.

Euclid’s Division Lemma (Statement)

If we divide a positive integer a from a positive integer b then we get two whole numbers as Quotient q and Remainder r. We can write this relationship like

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

OR

If there are two positive integers a and b then there will be two unique integers q and r satisfying the relation

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

Note – 1) Euclid’s Division Lemma can be used for all integers excluding zero(0).

2) In the above relation, q and r may be zero.

Example 1) Show that any positive integer can be written in the form 5q or 5q + 1 or 5q + 2 or 5q + 3 or 5q + 4, where q is an integer.

Solution – Let a and b be any two positive integers and we are taking b = 5

By Euclid’s lemma,     a = bq + r         where,  0 ≤ r < b

Here,      b = 5    so 0 ≤ r < 5    i.e. r = 0, 1, 2, 3, 4

Putting the values, b = 5 and r = 0 then  a = 5q + 0; a = 5q

b = 5 and r = 1 then  a = 5q + 1

b = 5 and r = 2 then  a = 5q + 2

b = 5 and r = 3 then  a = 5q + 3

b = 5 and r = 4 then  a = 5q + 4

Therefore, any positive integer can be written in the form of 5q, 5q + 1, 5q + 2, 5q + 3, and 5q + 4.    Ans.

Euclid’s Division Algorithm

Euclid’s Division Algorithm is based on Euclid’s division lemma and in this algorithm, we shall study its applications. In the Algorithm, there are some steps to solve problem-related to its applications. Here, we shall use its applications to find the HCF(Highest Common Factor) of two positive integers. HCF of two positive integers a and b is the greatest positive integer and both the positive integers a and b are divisible by it.

Steps to find HCF by Euclid’s Division Algorithm using Euclid’s Division Lemma

Step 1 – Let a and b be two positive integers (where a > b) then we shall get two whole numbers q and r after applying Euclid’s Division Lemma. So, the relationship will be

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

Step 2 – If we get the Remainder r = 0, then the value of Divisor b will be the Highest Common Factor (HCF) and if r ≠ 0 then we shall apply Euclid’s Division Lemma to Divisor b and Remainder r and we shall get another two whole numbers q` and r`

b = rq` + r`        where,      0 ≤ r` < r

Step 3 – If now we get the Remainder r` = 0, then the value of Divisor r will be the HCF and if r` ≠ 0 then we shall again apply Euclid’s Division Lemma to Divisor r and Remainder r`.

Step 4 – We shall continue the process until the Remainder becomes zero(0) and when the Remainder becomes zero, the value of the Divisor at that stage will be the required HCF.

Let’s Have Some Examples of it

Example 1) Find the HCF of 75 and 250 by Euclid’s Division Algorithm.

Solution – Step 1 – Here two positive integers are 75 and 250 and 250 > 75 so by Euclid’s Division lemma

250 = 75×3 + 25

Step 2 – Since the Remainder is not zero 25 ≠ 0 so we shall apply Euclid’s Division Lemma to Divisor 75 and Remainder 25.

75 = 25×3 + 0

Step 3 – Since the Remainder is zero in step 2 and the Divisor in this step is 25.

Therefore, the required HCF of 75 and 250 is 25.       Ans.

We can also understand by Division Process

Example 2) Use Euclid’s Division Lemma to find HCF of 196 and 38220.

Solution – Here 38220 > 196 so by Euclid’s Division Lemma

38220 = 196×195 + 0

Since the Remainder is zero in the first step so the HCF of 196 and 38220 is 196.              Ans.

We can also understand by Division Process

Example 3) Find the greatest number which divides 427 and 137 such that it leaves the remainder 7 in each case.

Solution – Here the remainder in each case is 7 so numbers will be 

427 – 7 = 420   and   137 – 7 = 130

Now we have to find the greatest number which divides 420 and 130 so we shall find the HCF of both numbers by Euclid’s Division Lemma

∵ 420 > 130

420 = 130×3 + 30

The remainder 30 ≠ 0, so Again using Euclid’s Lemma for 130 and 30

130 = 30×4 + 10

The remainder 10 ≠ 0, so Again using Euclid’s Division Lemma for 30 and 10

30 = 10×3 + 0

Now the Remainder is zero and Divisor is 10.

Thus the greatest number is 10.                Ans.

Euclid’s Division Lemma Class 10^th in Hindi

More About Euclid’s Division Lemma