# The Fundamental Theorem of Arithmetic

We have seen that any natural number can be written as a product of its prime factors. For instance,

**2 = 2**,

**4 = 2 × 2**,

**253 = × **.

**Fill the answers in ascending order only**.

The more we see, the more it seems that **all natural numbers can be obtained by multiplying prime numbers**.

Pick any natural number, let us say 44, if we factorize it with just primes we get

**44= x x **.

**Fill the answers in ascending order only**.

What about 1771 ?

**1771 = x x **.

**Fill the answers in ascending order only**.

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

**3 × 7 × 11 × 23 = **

**2 × 3 × 7 × 11 × 23 = **

Since the number of prime numbers are infinite and any composite number we take seems to be factorized into just prime numbers, we can make a conjecture that **any composite number can be written as a product of powers of prime. This is known as Fundamental Theorem of Arithmetic**.

We are going to use the factor tree with which we are all familiar. Let's take some large number, say, **32760** and factorise it as shown.

**Note: You can enter any number of your choice in the input field below.If you are unable to see all the numbers then select the entire factorization tree and move.Do not move the individual element.**

Upon factorised 32760 we get:

**32760 = 2 × 2 × 2 × 3 × 3 × 5 × 7 × as a product of primes**

**i.e., 32760 = **

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

Let us try another number, say, **123456789.**

This can be written as

.

We will also have to check if last two factors are primes or not! (Try it out for several other natural numbers using the above factorisation panel).

Upon trying out a variety of large numbers, we can see that **every number can be written as the product of powers of .** This statement is called the

**Fundamental Theorem of Arithmetic**

**Theorem 1.1** **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.

This theorem has crucial importance to the study of integers.

An equivalent version of the above theorem was (probably) first recorded as "Proposition 14" of Book IX in **Euclid’s Elements**, before it came to be known as the **Fundamental Theorem of Arithmetic.**

However, the first correct proof was given by Carl Friedrich Gauss in his *Disquisitiones Arithmeticae*.

**Note:** A composite number can be factorised as a

So, for example: we regard factorisation of 210 = 2 × 3 × 5 × 7 is same as writing 210 = 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 , except for the order of its factors.**

In general, given a composite number x, we factorise it as x = p1 p2 ...pn, where p1, p2,..., pn are primes and written in ascending order, i.e., p1 ≤ p2 ≤ . . . ≤ pn . If we combine the same primes, we will get powers of primes.The fundamental theorem also has a solved proof. Interested students can check it out at Proof of Fundamental Theorem of Arithmetic

Since the theorem is proved, it means that it will always hold true in the world of mathematics. That means we can take this as fact and then build on top of it for more interesting conclusions.

For example, consider the numbers , where n is a natural number. Is there is any value of n for which

**How do we begin to answer this question?**

If the number , for any n, were to end with the digit zero, then it would be divisible by the prime number

That is, the prime factorisation of would have to contain the prime 5. This is not possible because

**so the only prime in the factorisation of**4 n = 2 2 n ;

**is**4 n

So, the uniqueness of the Fundamental Theorem of Arithmetic guarantees that there are no other primes in the factorisation of So, there is

**ends with the digit zero.**4 n

**So, we took the uniqueness part of the theorem and applied it to quickly deduct the point that **

In general, given a composite number x, we factorise it as x = **p _{1} p_{2}... p_{n},** where

**p**are

_{1}, p_{2},..., p_{n}**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**

**= **

Once we have decided that the order will be ascending, then the way the number that 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.

Before moving forward, let's revise some HCFs and LCMs.

## HCF and LCM

We have already learnt how to find HCF and LCM in earlier classes. We can now see that **the prime factorization method actually uses the Fundamental Theorem of Arithmetic to gets its result**.

**Finding the HCF and LCM of 6 and 20**

**fill the answers in ascending order only**

Prime factors of 6 =

Prime factors of 20 =

i.e. 20 =

So HCF(6,20) =

**HCF(6, 20) = **

**LCM (6, 20) = 22 × 31×51 = Product of the greatest power of each prime factorinvolved in the numbers.**

In the example above, we can see that HCF(6, 20) × LCM(6, 20) =

But 6 x 20 is also equal to 120.

It can be proven that **for any two positive integers a,b:**

**HCF(a,b) x LCM(a,b) = a x b**

This will easily enable us to find the HCF or the LCM if the other is given.

Find the HCF of 96 and 404 by the prime factorisation method. Hence, find their LCM.

The prime factorisation of 96 and 404 gives:

96 =

**Therefore, the HCF of these two integers is**

Also, LCM (96, 404) =

Find the HCF and LCM of 6, 72 and 120, using the prime factorisation method.

We have : 6 = 2 × 3, 72 =

Here,

So, **HCF** (6, 72, 120) =

So, **LCM** (6, 72, 120) =

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