## 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

## Real Numbers

• Introduction
• Euclid’s Division Lemma
• The Fundamental Theorem of Arithmetic
• Revisiting Irrational Numbers
• Revisiting Rational Numbers and Their Decimal Expansions
• Summary

INTRODUCTION :

We have already studied about irrational numbers in 9th class. Now, we will study the real numbers and also about the important properties of positive integers for Euclid’s division algorithm and the Fundamental Theorem of Arithmetic.

Euclid’s division algorithm says us about divisibility of integers. It states that any positive integer ‘a’ can be divided by any other positive integer ‘b’ in such a way that it has ‘r’ remainder which is smaller than ‘b’. In fact it is a long division method. We also use it to compute the HCF of two positive integers.

The Fundamental Theorem of Arithmetic says us about the expression of positive integers as the product of prime integers. It states that every positive integer is either prime or a product of powers of prime integers. We have already known how to find HCF and LCM of positive integers by using the Fundamental Theorem of Arithmetic in previous class. Now, we will learn about irrationality of many numbers like etc. by applying this theorem. We know that the decimal representation of a rational number is either terminating or if repeating if not terminating. We have to use the Fundamental Theorem of Arithmetic to determine the nature of the decimal expansion of rational numbers.