**EUCLID’S DIVISION LEMMA :
**

Euclid was the first Greek Mathematician who gave a new way of thinking the study of geometry. He also made important contributions to the number theory. Euclid’s Lemma is one of them. It is a proven statement which is used to prove other statements.

Let ‘a’ and ‘b’ be any two positive integers. Then, there exist unique integers q and r such that

;

Now, we say ‘a’ as dividend, ‘b’ as divisor, ‘q’ as quotient and ‘r’ as remainder.

Dividend = (divisor quotient) + remainder

* Example: *Let 578 be divided by 16.

36 is as quotient and 2 as remainder.

In this case :

Dividend = 578

Divisor = 16

Quotient = 36

And remainder = 2

Dividend = (quotient divisor) + remainder

Hence, 578 = (36 16) + 2

To get the HCF of two positive integers, let ‘c’ and ‘d’, with c > d, follow as :

**(i)** Applying Euclid’s Lemma,

**(ii) **If r = 0, d is the HCF of c and d.

If then applying the division lemma to d and r.

**(iii)** We can continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

This algorithm works because HCF (c,d) = HCF (d,r)

Where the symbol HCF (c,d) denotes the HCF of c and d etc.

* Example: *Use Euclid’s algorithm to find HCF of 425 and 40

* Solution: *Let a = 425 and b = 40

By Euclid’s division lemma; we have

…. (i)

By using the above theorem, we observe that the common divisors of a = 425 and b = 40 are also the common divisors of b = 40 and r_{1} = 25 and vice-versa.

Applying Euclid’s division lemma on divisor b = 40 and remainder r_{1} = 25,

We get …. (ii)

; where q_{2} = 1 and r_{2} = 15

Again using the above theorem, we find that, the common divisors of r_{1} = 25 and r_{2} = 15 are the common divisors of b = 40 and r_{1} = 25 and vice-versa. But the common divisors of b = 40 and r_{1} = 25 are the common divisors of a = 425 and b = 40 and vice-versa.

Applying Euclid’s division lemma on r_{1} = 25 and r_{2} = 15, we get

…. (iii)

r_{1 }= r_{2}q_{3} + r_{3}, where q_{3} = 1 and r_{3} = 10

Again by using the above theorem, we find that common divisors of r_{2} = 15 and r_{3} = 10 are the common divisors of a = 425 and b = 40 and vice-versa.

Now, Using Euclid’s division lemma on r_{2} = 15 and r_{3} = 10, we get

…. (iv)

; where q_{4} = 1 and r_{4} = 5

Again by using the above theorem, we find that, the common divisors of r_{2} = 15 and r_{3} = 10 are the common divisors of a = 425 and b = 40 and vice-versa.

Using Euclid’s division lemma on r_{3} = 10 and r_{4} = 5, we get

…. (v)

Hence, r_{4} = 5 is a divisor of r_{3} = 10 and r_{4} = 5. Also, it is the greatest common divisor (or HCF) of r_{3} and r_{4}. So, r_{4} = 5 is the greatest common divisor (or HCF) of a = 425 and b = 40. We also observe that r_{4} = 5 is the last non-zero remainder in the above process of repeated application of Euclid’s division lemma on the divisor and the remainder in the next step.

The set of equation (i) to (v) is called Euclid’s division algorithm for 425 and 40. The last divisor, or the last but non-zero remainder 4 is the HCF (or GCD) of 425 and 40.

The above process of finding HCF can also be carried out by successive divisions as follows:

(i) Euclid’s division lemma and algorithm are so closely interlinked that it is often called division algorithm.

(ii) Euclid’s Division Algorithm is stated for only positive integers except zero. i.e., .

*Example 3*:

A sweet seller has 840 kaju barfis and 260 badam barfis. He wants to stack them in such a way that each stack has the same number, and they take up the least area of the tray. What is the number of barfis that can be placed in each stack for this purpose?

** Solution**. The area of the tray that is used up will be the least. For this, we find HCF (840, 260). Then this number will give the maximum number of barfis in each stack and the number of stacks will then be the least.

Now, applying Euclid’s algorithm to find their HCF, we have

840 = 260 3 + 60

260 = 60 4 + 20

60 = 20 3 + 0

Hence, HCF of 840 and 260 is 20.

So, the sweet seller can make stacks of 10 for both kinds of barfi