# Real Numbers: Euclid’s Division Lemma

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 $\displaystyle \times$ 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 $\displaystyle \times$ divisor) + remainder

Hence, 578 = (36 $\displaystyle \times$ 16) + 2

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

(i) Applying Euclid’s Lemma, $\displaystyle c=dq+r;\,0\le r

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

If $\displaystyle r\ne 0,$ 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  $\displaystyle 425=40\times 10+25$ …. (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 r1 = 25 and vice-versa.

Applying Euclid’s division lemma on divisor b = 40 and remainder r1 = 25,

We get $\displaystyle 40=25\times 1+15$ …. (ii)  $\displaystyle b=q_{2}^{r},+{{r}_{2}}$; where q2 = 1 and r2 = 15

Again using the above theorem, we find that, the common divisors of r1 = 25 and r2 = 15 are the common divisors of b = 40 and r1 = 25 and vice-versa. But the common divisors of b = 40 and r1 = 25 are the common divisors of a = 425 and b = 40 and vice-versa.

Applying Euclid’s division lemma on r1 = 25 and r2 = 15, we get $\displaystyle 25=15\times 1+10$ …. (iii)  $\displaystyle \Rightarrow$ r1 = r2q3 + r3, where q3 = 1 and r3 = 10

Again by using the above theorem, we find that common divisors of r2 = 15 and r3 = 10 are the common divisors of a = 425 and b = 40 and vice-versa.

Now, Using Euclid’s division lemma on r2 = 15 and r3 = 10, we get $\displaystyle 15=10\times 1+5$ …. (iv)  $\displaystyle \Rightarrow$ $\displaystyle r{{ & }_{2}}={{r}_{3}}\times {{q}_{4}}+{{r}_{4}}$; where q4 = 1 and r4 = 5

Again by using the above theorem, we find that, the common divisors of r2 = 15 and r3 = 10 are the common divisors of a = 425 and b = 40 and vice-versa.

Using Euclid’s division lemma on r3 = 10 and r4 = 5, we get $\displaystyle 15=5\times 3+0$ …. (v) Hence, r4 = 5 is a divisor of r3 = 10 and r4 = 5. Also, it is the greatest common divisor (or HCF) of r3 and r4. So, r4 = 5 is the greatest common divisor (or HCF) of a = 425 and b = 40. We also observe that r4 = 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., $\displaystyle b\ne 0$.

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 $\displaystyle \times$ 3 + 60

260    =    60 $\displaystyle \times$ 4 + 20

60    =    20 $\displaystyle \times$ 3 + 0

Hence, HCF of 840 and 260 is 20.

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