**INTRODUCTION:
**

We have already studied about irrational numbers in previous 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.

**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 1: *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

**Note:
**

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 2: *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:

**Note:
**

(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.