##### Grade X - Mathematics

**Author:**

Rahul Chandra Saha

M.Sc., Mathematics

### Introduction

In class IX, you came to know about real numbers. The two complementary sub-sets of real numbers are the rational numbers and irrational numbers. You have learned about them. In this chapter we will discuss more about the irrationals, Fundamental Theorem of Arithmetic and related applications. But before these one obvious question arises ”is there any rule of dividing the numbers and if so then how to construct the algorithm for it?”

### Euclid’s Division Lemma

Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b.

This result was first recorded in Book VII of Euclid’s Elements. The division algorithm is based on the Euclid’s Division lemma. *Think Yourself*

Q1. What is algorithm? Is there any similarities between computer algorithm and algorithm we are dis-

cussing?

Q2. What is lemma?

### Euclid’s Division Algorithm

It is a algorithm or technique to compute the HCF(Highest Common Factor) of two given positive integers.

Let us try to extract the algorithm from an example. Suppose we need to find the HCF of the integers 413 and 42. We will start with the larger number,i.e., 413 and then use the Euclid’s Division Lemma to get-

\[413 = 42 × 9 + 35.\]

Now consider divisor 42 and remainder 35 and applying division lemma we get,

\[42 = 35 × 1 + 7.\]

Again consider the divisor 35 and remainder 7. On applying division lemma we get,

\[35 = 7 × 5 + 0\]

Here the remainder has become zero. Thus we can not proceed further. Our claim is that 7 is the H.C.F. or G.C.D.(Greatest Common Divisor) of 413 and 42 is 7. Let us check. 413 = 7 × 59 and 42 = 7 × 6. Thus H.C.F (413, 42) = 7.

Euclid’s Division Algorithm. To obtain the HCF of two arbitrary positive integers $c$ and $d$ with $d < c$, follow the following steps-**1.** Applying Division Lemma to c and d find integers q and r such that

\[c = d × q + r, 0 ≤ r < d\]**2.** If $r = 0$ then $HCF (c, d) = d$. If $r \neq 0$ apply division lemma to $d$ and $r$.

**3.** Continue the process till the remainder is zero. The divisor at the last stage will be the required HCF.

** Think yourself:** Why the method works?

**Problem**. Apply Euclid’s Algorithm to find HCF (250, 100).

### The Fundamental Theorem of Arithmetic

**Theorem**.

Every composite number can be factorised as a product of primes,and this factorisation is unique,apart from the order in which the prime factors occur.

**Example 1**. Factorise 240.**Solution** . $240 = 2 × 120 = 2^{2} × 60 = 2^{3 }× 30 = 2^4 × 15 = 2 ^4 × 3 × 5$

**Example 2**. Construct the factor tree of 30.

**Example 3.** Find the HCF of 55 and 90 by prime factorisation method. Hence find their LCM.

Solution . Prime factorisation of 55 and 90 gives

\[55 = 5 × 11 \text{ and } 90 = 2 × 3 2 × 5.\]

Therefore, \[HCF (55, 90) = 5.\]

Also we know that,

\[HCF × LCM =\text{Multiplication of two numbers}.\]

Hence,

\[\text{LCM} = \frac{55\times90}{5} = 990 \]