CBSE Tutorials

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

    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₁ = 25 and vice-versa.

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

    ; where q₂ = 1 and r₂ = 15

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

    Applying Euclid’s division lemma on r₁ = 25 and r₂ = 15, we get

        r₁ = r₂q₃ + r₃, where q₃ = 1 and r₃ = 10

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

    Now, Using Euclid’s division lemma on r₂ = 15 and r₃ = 10, we get

         ; where q₄ = 1 and r₄ = 5

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

    Using Euclid’s division lemma on r₃ = 10 and r₄ = 5, we get

    Hence, r₄ = 5 is a divisor of r₃ = 10 and r₄ = 5. Also, it is the greatest common divisor (or HCF) of r₃ and r₄. So, r₄ = 5 is the greatest common divisor (or HCF) of a = 425 and b = 40. We also observe that r₄ = 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.