The Fundamental Theorem of Arithmetic, on the other hand, has to do something with multiplication of positive integers. Every Composite Number can be expressed as a product of primes in a unique way — this important fact is the Fundamental Theorem of Arithmetic. Again, while it is a result that is easy to state and understand, it has some very deep and significant applications in the field of mathematics. We use the Fundamental Theorem of Arithmetic for two main applications. First, we use it to prove the irrationality of many of the numbers, such as √2, √3 and √5 . Second, we apply this theorem to explore when exactly the decimal expansion of a rational number, say p/q,(q ≠ 0), is terminating and when it is nonterminating repeating. We do so by looking at the prime factorisation of the denominator q of p/q . You will see that the prime factorisation of q will completely reveal the nature of the decimal expansion of p/q .

**1.2 . Euclid’s Division Lemma
**

**Theorem 1.1 (Euclid’s Division Lemma) :** Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b.

Euclid’s division algorithm is a technique to compute the Greatest Common Divisor or Highest Common Factor (HCF) of two given positive integers. Recall that the HCF of two positive integers *a* and *b* is the largest positive integer *d* that divides both *a* and *b*.

** Let us see how the algorithm works, through an example first. **

Suppose we need to find the HCF of the integers 455 and 42. We start with the larger integer, that is, 455. Then we use Euclid’s lemma to get 455 = 42 × 10 + 35

Now consider the divisor 42 and the remainder 35, and apply the division lemma to get 42 = 35 × 1 + 7

Now consider the divisor 35 and the remainder 7, and apply the division lemma to get 35 = 7 × 5 + 0 Notice that the remainder has become zero, and we cannot proceed any further.

We claim that the HCF of 455 and 42 is the divisor at this stage, i.e., 7.

We can easily verify this by listing all the factors of 455 and 42. Why does this method work? It works because of the following result. So, **let us state Euclid’s division algorithm clearly. **

To obtain the HCF of two positive integers, say *c* and *d*, with *c > d*, follow the steps below:

* Step 1 *: Apply Euclid’s division lemma, to

*c*and

*d*. So, we find whole numbers,

*q*and

*r*such that

*c = dq + r, 0 ≤ r < d.*

* Step 2 :* If

*r = 0, d*is the HCF of

*c*and

*d*. If

*r ≠ 0*, apply the division lemma to

*d and r*.

* Step 3 :* 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 1 :** Use Euclid’s algorithm to find the HCF of 4052 and 12576.

**Solution :**

** Step 1 :** Since 12576 > 4052, we apply the division lemma to 12576 and 4052, to get 12576 = 4052 × 3 + 420

**Step 2 :** Since the remainder 420 ≠ 0, we apply the division lemma to 4052 and 420, to get 4052 = 420 × 9 + 272

**Step 3 :** We consider the new divisor 420 and the new remainder 272, and apply the division lemma to get 420 = 272 × 1 + 148

We consider the new divisor 272 and the new remainder 148, and apply the division lemma to get 272 = 148 × 1 + 124

We consider the new divisor 148 and the new remainder 124, and apply the division lemma to get 148 = 124 × 1 + 24

We consider the new divisor 124 and the new remainder 24, and apply the division lemma to get 124 = 24 × 5 + 4

We consider the new divisor 24 and the new remainder 4, and apply the division lemma to get 24 = 4 × 6 + 0

**The remainder has now become zero, so our procedure stops**. Since the divisor at this stage is 4, the HCF of 12576 and 4052 is 4.

Notice that 4 = HCF (24, 4) = HCF (124, 24) = HCF (148, 124) = HCF (272, 148) = HCF (420, 272) = HCF (4052, 420) = HCF (12576, 4052).

Euclid’s division algorithm is not only useful for calculating the HCF of very large numbers, but also because it is one of the earliest examples of an algorithm that a computer had been programmed to carry out.

**Example 2 :** Show that every positive even integer is of the form 2q, and that every positive odd integer is of the form 2q + 1, where q is some integer.

**Solution :**

Let *a* be any positive integer and *b = 2. *

Then, by Euclid’s algorithm, *a = 2q + r*, for some integer *q ≥ 0,* and *r = 0 or r = 1*, because *0 ≤ r < 2.* So, *a = 2q or 2q + 1*.

If *a* is of the form *2q*, then a is an even integer. Also, a positive integer can be either even or odd. Therefore, any positive odd integer is of the form *2q + 1*.

**Example 3 :** Show that any positive odd integer is of the form 4q + 1 or 4q + 3, where q is some integer.

**Solution :**

Let us start with taking a, where a is a positive odd integer.

We apply the division algorithm with *a* and *b = 4*. Since *0 ≤ r < 4,* the possible remainders are 0, 1, 2 and 3. That is, *a* can be *4q, or 4q + 1, or 4q + 2, or 4q + 3*, where *q* is the quotient.

However, since *a* is odd, *a* cannot be *4q* or *4q + 2* (since they are both divisible by 2). Therefore, any odd integer is of the form *4q + 1 or 4q + 3*.

**Example 4 :** A sweetseller has 420 *kaju barfis* and 130 *badam barfis*. She 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 maximum number of *barfis* that can be placed in each stack for this purpose?

**Solution :**

This can be done by trial and error.

But to do it systematically, we find HCF (420, 130). Then this number will give the maximum number of *barfis* in each stack and the number of stacks will then be the least. The area of the tray that is used up will be the least.

Now, let us use ** Euclid’s algorithm **to find their HCF.

We have : 420 = 130 × 3 + 30 130 = 30 × 4 + 10 30 = 10 × 3 + 0

So, the HCF of 420 and 130 is 10.

Therefore, the sweetseller can make stacks of 10 for both kinds of barfi

Click here Real Numbers EXERCISE 1.1 for related solved exercise problems.

**1.3 The Fundamental Theorem of Arithmetic**

Take any collection of prime numbers, say 2, 3, 7, 11 and 23.

If we multiply some or all of these numbers, allowing them to repeat as many times as we wish, we can produce a large collection of positive integers (In fact, infinitely many).

Let us list a few :

7 × 11 × 23 = 1771

3 × 7 × 11 × 23 = 5313

2 × 3 × 7 × 11 × 23 = 10626

2^{3} × 3 × 7^{3} = 8232

2^{2} × 3 × 7 × 11 × 23 = 21252 and so on

Let us take another example, we are going to use the factor tree with which you are all familiar. Let us take some large number, say, 32760, and factorise it as shown :

So we have factorised 32760 as 2 × 2 × 2 × 3 × 3 × 5 × 7 × 13 as a product of primes, i.e., 32760 = 2^{3} × 3^{2} × 5 × 7 × 13 as a product of powers of primes.

Let us try another number, say, 123456789. This can be written as 3^{2} × 3803 × 3607. Of course, you have to check that 3803 and 3607 are primes! (Try it out for several other natural numbers yourself.)

This leads us to a conjecture that every composite number can be written as the product of powers of primes.

In fact, this statement is true, and is called the **Fundamental Theorem of Arithmetic** because of its basic crucial importance to the study of integers. Let us now formally state this theorem.

**Theorem 1.2 (Fundamental Theorem of Arithmetic) : ***Every composite number can be expressed ( factorised) as a product of primes, and this factorisation is unique, apart from the order in which the prime factors occur.*

The **Fundamental Theorem of Arithmetic** says that *every composite number can be factorised as a product of primes*.

Actually it says more. It says that given any composite number it can be factorised as a product of prime numbers in a **‘unique’** way, except for the order in which the primes occur. That is, given any composite number there is one and only one way to write it as a product of primes, as long as we are not particular about the order in which the primes occur. So, for example, we regard 2 × 3 × 5 × 7 as the same as 3 × 5 × 7 × 2, or any other possible order in which these primes are written. This fact is also stated in the following form:

The prime factorisation of a natural number is unique, except for the order of its factors. In general, given a composite number x, we factorise it as x = p_{1} p_{2} … p_{n} , where p_{1}, p_{2} ,…, p_{n} are primes and written in ascending order, i.e., p_{1} ≤ p_{2} ≤ . . . ≤ p_{n} .

If we combine the same primes, we will get powers of primes. For example, 32760 = 2 × 2 × 2 × 3 × 3 × 5 × 7 × 13 = 2^{3} × 3^{2} × 5 × 7 × 13

Once we have decided that the order will be ascending, then the way the number is factorised, is unique. The Fundamental Theorem of Arithmetic has many applications, both within mathematics and in other fields.

Let us look at some examples.

**Example 5 :** Consider the numbers 4^{n} , where n is a natural number. Check whether there is any value of n for which 4^{n} ends with the digit zero.

**Solution: **

If the number 4^{n} , for any n, were to end with the digit zero, then it would be divisible by 5. That is, the prime factorisation of 4^{n} would contain the prime 5. This is not possible because 4^{n} = (2)2^{n} ; so the only prime in the factorisation of 4^{n} is 2. So, the uniqueness of the Fundamental Theorem of Arithmetic guarantees that there are no other primes in the factorisation of 4^{n} . So, there is no natural number n for which 4^{n} ends with the digit zero.

**Note: **You have already learnt how to find the HCF and LCM of two positive integers using the Fundamental Theorem of Arithmetic in earlier classes, without realising it! This method is also called the prime factorisation method. Let us recall this method through an example.

**Example 6 :** Find the LCM and HCF of 6 and 20 by the prime factorisation method.

**Solution :**

We have,

6 = 2^{1} × 3^{1} and 20 = 2 × 2 × 5 = 2^{2} × 5^{1} . You can find HCF(6, 20) = 2 and LCM(6, 20) = 2 × 2 × 3 × 5 = 60, as done in your earlier classes.

Note that HCF(6, 20) = 2^{1} = **Product of the smallest power of each common prime factor in the numbers. **

LCM (6, 20) = 2^{2} × 3^{1} × 5^{1} = **Product of the greatest power of each prime factor, involved in the numbers. **

From the example above, you might have noticed that HCF(6, 20) × LCM(6, 20) = 6 × 20. In fact, we can verify that for **any two positive integers a and b, HCF (a, b) × LCM (a, b) = a × b.** We can use this result to find the LCM of two positive integers, if we have already found the HCF of the two positive integers.

**Example 7 :** Find the HCF of 96 and 404 by the prime factorisation method. Hence, find their LCM. **Solution :** The prime factorisation of 96 and 404 gives:

96 = 2^{5} × 3,

404 = 2^{2} × 101

Therefore, the HCF of these two integers is 2^{2} = 4.

Also,

LCM (96, 404) = (96 x 404)/(HCF(96,404)) = (96 x 404)/ 4 = 9696.

**Example 8 :** Find the HCF and LCM of 6, 72 and 120, using the prime factorisation method.

**Solution :**

We have,

6 = 2 × 3, 72 = 2^{3} × 3^{2} , 120 = 2^{3} × 3 × 5

Here, 2^{1} and 3^{1} are the smallest powers of the common factors 2 and 3 respectively.

So,

HCF (6, 72, 120) = 2^{1} × 3^{1} = 2 × 3 = 6

2^{3} , 3^{2} and 5^{1} are the greatest powers of the prime factors 2, 3 and 5 respectively involved in the three numbers.

So, LCM (6, 72, 120) = 2^{3} × 3^{2} × 5^{1} = 360

**Remark :** Notice, 6 × 72 × 120 ≠ HCF (6, 72, 120) × LCM (6, 72, 120). So, the product of three numbers is not equal to the product of their HCF and LCM.

click Real number EXERCISE 1.2 for related exercise solved problems..

**1.4 Revisiting Irrational Numbers**

A number ‘s’ is called irrational if it cannot be written in the form , p/q where p and q are integers and q ≠ 0. Some examples of irrational numbers, are : √2, √3, √15 , -√2/√3, 0.10110111011110 . . . , π etc.

Before we prove that √2 is irrational, we need the following theorem, whose proof is based on the Fundamental Theorem of Arithmetic

**Theorem 1.3 :** *Let p be a prime number. If p divides a2 , then p divides a, where a is a positive integer.*

**Proof :** Let the prime factorisation of a be as follows:

** **a = p_{1} p_{2} . . . p_{n} , where p_{1} ,p_{2} , . . ., p_{n} are primes, not necessarily distinct.

Therefore, a^{2} = (p_{1} p_{2} . . . p_{n} ) (p_{1} p_{2} . . . p_{n} )= p_{1}^{2} p_{2}^{2} . . . p_{n}^{2}

Now, we are given that p divides a^{2} . Therefore, from the Fundamental Theorem of Arithmetic, it follows that p is one of the prime factors of a^{2} . However, using the uniqueness part of the Fundamental Theorem of Arithmetic, we realise that the only prime factors of a^{2} are p_{1} p_{2} . . . p_{n}. So p is one of p_{1} p_{2} . . . p_{n}.

Now, since a = p_{1} p_{2} . . . p_{n}, p divides a.

**We are now ready to give a proof that √2 is irrational.**

**Theorem 1.4 : √2 is irrational.**

Proof :

Let us assume, to the contrary, that √2 is rational.

So, we can find integers r and s (≠ 0) such that *√2 = r/s* .

Suppose r and s have a common factor other than 1.

Then, we divide by the common factor to get √2 = *a/b,* where a and b are coprime. So, b √2 = a.

Squaring on both sides and rearranging, we get 2b^{2} = a^{2} . Therefore, 2 divides a^{2} . Now, by **Theorem 1.3,** it follows that 2 divides *a*. So, we can write a = 2c for some integer c.

Substituting for a, we get 2b^{2} = 4c^{2} , that is, b^{2} = 2c^{2} . This means that 2 divides b^{2} , and so 2 divides b (again using Theorem 1.3 with p = 2). Therefore, *a* and *b* have at least 2 as a common factor.

But this contradicts the fact that *a* and *b* have no common factors other than 1.

This contradiction has arisen because of our incorrect assumption that √2 is rational. So, we conclude that **√2 is irrational.**

**Example 9 :** Prove that 3 is irrational.

**Solution** :

Let us assume, to the contrary, that √3 is rational. That is, we can find integers *a and b* (≠ 0) such that 3 = *a/b* ⋅ Suppose *a* and *b* have a common factor other than 1, then we can divide by the common factor, and assume that *a and b* are coprime.

So, *b* √3 = *a*

Squaring on both sides, and rearranging, we get *3b ^{2} = a^{2}* .

Therefore, *a ^{2}* is divisible by 3, and by Theorem 1.3, it follows that

*a*is also divisible by 3.

So, we can write *a = 3c*, for some integer *c.*

Substituting for *a*, we get* 3b ^{2} = 9c^{2}* , that is,

*b*.

^{2}= 3c^{2}This means that *b ^{2}* is divisible by 3, and so b is also divisible by 3 (using Theorem 1.3 with p = 3). Therefore,

*a and b*have at least 3 as a common factor.

But this contradicts the fact that *a and b* are coprime. This contradiction has arisen because of our incorrect assumption that √3 is rational. So, we conclude that √3 is irrational.

**Example 10 :** Show that 5– √3 is irrational.

**Solution : **

Let us assume, to the contrary, that 5– √3 is rational. That is, we can find coprime a and b (b ≠ 0) such that *5-** √3 = a/b.*

Therefore, *(5 – **(a/b))=* √3

*⋅* Rearranging this equation, we get √3 = (5 – (a/b)) = (5b – a)/b⋅ Since *a* and *b* are integers, we get *(5 – a/b*) is rational, and so √3 is rational.

But this contradicts the fact that √3 is irrational. This contradiction has arisen because of our incorrect assumption that *(5 – **√3)* is rational.

So, we conclude that *(5 – **√3)* is irrational.

**Example 11 :** Show that 3 √2 is irrational.

**Solution :**

Let us assume, to the contrary, that 3 √2 is rational.

That is, we can find coprime *a and b (b ≠ 0)* such that *3** √2 = a/b*⋅

Rearranging, we get *√2 = a/3b* ⋅

Since 3, *a and b* are integers, *a/3b* is rational, and so √2 is rational.

But this contradicts the fact that √2 is irrational. So, we conclude that 3 √2 is irrational.

Click Real Numbers exercise 1.3

**1.5 Revisiting Rational Numbers and Their Decimal Expansions**

A rational number, say *p/q q ≠ 0,* and explore exactly when the decimal expansion of *p/q* is terminating and when it is non-terminating repeating (or recurring)

Let us consider the following rational numbers :

(i) 0.375

(ii) 0.104

(iii) 0.0875

(iv) 23.3408

Now,

(i) 0.375 = (0.375)/(1000) = 375/10³

(ii) 0.104 = (0.104)/(1000) = 104/10³

(iii) 0.0875 = (0.0875)/(10000) = 875/10^{4}

(iv) 23.3408 = (23.3408)/(10000) = 233408/10^{4}

As one would expect, they can all be expressed as rational numbers whose denominators are powers of 10. Let us try and cancel the common factors between the numerator and denominator and see what we get :

It appears that, we have converted a real number whose decimal expansion terminates into a rational number of the form , *p q* where *p* and *q* are coprime, and the prime factorisation of the denominator (that is, *q*) has only powers of 2, or powers of 5, or both. We should expect the denominator to look like this, since powers of 10 can only have powers of 2 and 5 as factors

Even though, we have worked only with a few examples, you can see that any real number which has a decimal expansion that terminates can be expressed as a rational number whose denominator is a power of 10. Also the only prime fators of 10 are 2 and 5. So, cancelling out the common factors between the numerator and the denominator, we find that this real number is a rational number of the form , *p/q* where the prime factorisation of *q* is of the form *2 ^{n} 5^{m}*, and

*n, m*are some non-negative integers. Let us write our result formally:

** Theorem 1.5 :** Let x be a rational number whose decimal expansion terminates. Then x can be expressed in the form ,

*p/q*where

*p and q*are coprime, and the prime factorisation of

*q*is of the form

*2*where

^{n}5^{m},*n, m*are non-negative integers

You are probably wondering what happens the other way round in ** Theorem 1.5**. That is, if we have a rational number of the form ,

*p/q*and the prime factorisation of

*q*is of the form

*2*, where

^{n}5^{m}*n, m*are non negative integers, then does

*p/q*have a terminating decimal expansion?

Let us see if there is some obvious reason why this is true. You will surely agree that any rational number of the form , *a/b* where *b* is a power of 10, will have a terminating decimal expansion. So it seems to make sense to convert a rational number of the form *p/q* , where *q* is of the form *2 ^{n} 5^{m}*, to an equivalent rational number of the form ,

*a/b*where

*b*is a power of 10. Let us go back to our examples above and work backwards

So, these examples show us how we can convert a rational number of the form *p/q ,* where *q* is of the form 2^{n} 5^{m}, to an equivalent rational number of the form , *a/b* where *b* is a power of 10. Therefore, the decimal expansion of such a rational number terminates. Let us write down our result formally

** Theorem 1.6 :** Let

*x = p/q*be a rational number, such that the prime factorisation of

*q*is of the form

*2*where

^{n}5^{m},*n, m*are non-negative integers. Then

*x*has a decimal expansion which terminates.

** Theorem 1.7** : Let

*x = p/q*be a rational number, such that the prime factorisation of

*q*is not of the form

*2*, where

^{n}5^{m}*n, m*are non-negative integers. Then,

*x*has a decimal expansion which is non-terminating repeating (recurring). From the discussion above, we can conclude that the decimal expansion of every rational number is either terminating or non-terminating repeating

click here Real numbers Exercise 1.4 to get solved problems

**POINTS TO REMEMEBER:**

Given positive integers__Euclid’s division lemma :__*a*and*b*, there exist whole numbers*q*and*r*satisfying*a = bq + r, 0 ≤ r < b.*This is based on Euclid’s division lemma. According to this, the HCF of any two positive integers__Euclid’s division algorithm :__*a*and*b*, with*a > b*, is obtained as follows:

** Step 1** : Apply the division lemma to find

*q*and

*r*where

*a = bq + r, 0 ≤ r < b*.

** Step 2 :** If

*r = 0*, the HCF is

*b*. If

*r ≠ 0,*apply Euclid’s lemma to

*b*and

*r*.

** Step 3 :** Continue the process till the remainder is zero. The divisor at this stage will be HCF

*(a, b).*Also, HCF

*(a, b)*= HCF

*(b, r).*

Every composite number can be expressed (factorised) as a product of primes, and this factorisation is unique, apart from the order in which the prime factors occur.__The Fundamental Theorem of Arithmetic :__- If
*p*is a prime and*p*divides*a*, then^{2}*p*divides*q*, where*a*is a positive integer. - √2, √3 are irrationals.
- Let
*x*be a rational number whose decimal expansion terminates. Then we can express*x*in the form*p/q ,*where*p*and*q*are coprime, and the prime factorisation of*q*is of the form*2*, where^{n}5^{m}*n, m*are non-negative integers. - Let
*x = p/q*be a rational number, such that the prime factorisation of*q*is of the form*2*where^{n}5^{m},*n, m*are non-negative integers. Then*x*has a decimal expansion which terminates. - Let
*x = p/q*be a rational number, such that the prime factorisation of*q*is not of the form*2*where^{n}5^{m},*n, m*are non-negative integers. Then*x*has a decimal expansion which is non-terminating repeating (recurring).

Pingback: X- Table of Contents – Breath Math