Fundamental Theorem of Arithmetic

1.1 Introduction

In Class IX, you began exploring the world of real numbers^? and encountered irrational numbers. We continue our discussion on real numbers in this chapter. We begin with two very important properties of positive integers, namely Euclid's division algorithm and the Fundamental Theorem of Arithmetic^?.

Euclid's division algorithm, as the name suggests, has to do with divisibility of integers. Stated simply, it says any positive integer \(a\) can be divided by another positive integer \(b\) in such a way that it leaves a remainder \(r\) that is smaller than \(b\). You probably recognise this as the usual long division process. Although it is quite easy to state and understand, it has many applications related to the divisibility properties of integers.

The Fundamental Theorem of Arithmetic, on the other hand, has to do with multiplication of positive integers. You already know that every composite number can be expressed as a product of primes in a unique way -- this important fact is the Fundamental Theorem of Arithmetic. We use it for two main applications:

1. To prove the irrationality of numbers such as \(\sqrt{2}\), \(\sqrt{3}\) and \(\sqrt{5}\).
2. To explore when exactly the decimal expansion of a rational number \(\frac{p}{q}\) (\(q \neq 0\)) is terminating and when it is non-terminating repeating.

1.2 The Fundamental Theorem of Arithmetic

In your earlier classes, you have seen that any natural number can be written as a product of its prime factors. For instance, \(2 = 2\), \(4 = 2 \times 2\), \(253 = 11 \times 23\), and so on. Now, let us try and look at natural numbers from the other direction. That is, can any natural number be obtained by multiplying prime numbers?

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:

Now, let us suppose your collection of primes includes all the possible primes. Does it contain only a finite number of integers, or infinitely many? In fact, there are infinitely many primes. So, if we combine all these primes in all possible ways, we will get an infinite collection of numbers, all the primes and all possible products of primes.

The question is -- can we produce all the composite numbers this way? Before we answer this, let us factorise a large number, say 32760, and factorise it as shown in the factor tree below.

So we have factorised 32760 as \(2 \times 2 \times 2 \times 3 \times 3 \times 5 \times 7 \times 13\), which is a product of primes. That is, \(32760 = 2^3 \times 3^2 \times 5 \times 7 \times 13\), written as a product of powers of primes.

Let us try another number, say 123456790. This can be written as \(3^2 \times 3803 \times 3607\). (Of course, you have to check that 3803 and 3607 are primes!) 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.

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. So, for example, we regard \(2 \times 3 \times 5 \times 7\) as the same as \(3 \times 5 \times 7 \times 2\), or any other possible order in which these primes are written. This fact is also stated in the following form:

In general, given a composite number \(x\), we factorise it as \(x = p_1 p_2 \ldots p_n\) where \(p_1, p_2, \ldots, p_n\) are primes and written in ascending order, i.e., \(p_1 \le p_2 \le \ldots \le p_n\). If we combine the same primes, we will get powers of primes. For example:

\(32760 = 2 \times 2 \times 2 \times 3 \times 3 \times 5 \times 7 \times 13 = 2^3 \times 3^2 \times 5 \times 7 \times 13\)

Once we have decided that the order will be ascending, then the way the number is factorised is unique.

HCF and LCM using the Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic has many applications, both within mathematics and in other fields. Let us look at some examples.

Example 1: Can \(4^n\) end with the digit zero?

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 2: Find the LCM and HCF of 6 and 20 by the prime factorisation method.

Example 3: Find the HCF and LCM of 96 and 404.

Example 4: Find the HCF and LCM of 6, 72 and 120.