The Fundamental Theorem of Arithmetic

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 × 2, 253 = 11 × 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? Let us see.

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 × 7³ = 8232

2² × 3 × 7 × 11 × 23 = 21252 and so on.

Now, let us suppose your collection of primes includes all the possible primes. What is your guess about the size of this collection? Does it contain only a finite number of integers, or infinitely many? Infact, 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? What do you think? Do you think that there may be a composite number which is not the product of powers of primes? Before we answer this, let us factorise positive integers, that is, do the opposite of what we have done so far.

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² × 5 × 7 × 13 as a product of powers of primes. Let us try another number, say, 123456789. This can be written as 3² × 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)

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₁ p₂ ... p_n, where p₁, p₂,..., p_n are primes and written in ascending order, i.e.,\(% MathType!MTEF!2!1!+- % feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiCamaaBa % aaleaacaaIXaaabeaakiabgsMiJkaadchadaWgaaWcbaGaaGOmaaqa % baGccqGHKjYOcaGGUaGaaiOlaiaac6cacaGGUaGaaiOlaiaac6caca % GGUaGaaiOlaiaac6cacaGGUaGaaiOlaiaac6cacaGGUaGaeyizImQa % amiCamaaBaaaleaacaWGUbaabeaaaaa!4A00! {p_1} \le {p_2} \le ............. \le {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² × 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 and 6 (The Fundamental Theorem of Arithmetic)

Example 5 and 6 (The Fundamental Theorem of Arithmetic)

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

Solution :

If the number 4ⁿ, for any n, were to end with the digit zero, then it would be divisible by 5. That is, the prime factorisation of 4ⁿ would contain the prime 5. This is not possible because 4ⁿ = (2)²ⁿ; so the only prime in the factorisation of 4ⁿ is 2. So, the uniqueness of the Fundamental Theorem of Arithmetic guarantees that there are no other primes in the factorisation of 4ⁿ. So, there is no natural number n for which 4ⁿ ends 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 6 : Find the LCM and HCF of 6 and 20 by the prime factorisation method.

Solution :

We have : 6 = 2¹ × 3¹ and 20 = 2 × 2 × 5 = 2² × 5¹.

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¹ = Product of the smallest power of each common prime factor in the numbers.

LCM (6, 20) = 2² × 3¹ × 5¹ = 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 and 8 (The Fundamental Theorem of Arithmetic)

Example 7 and 8 (The Fundamental Theorem of Arithmetic)

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⁵ × 3, 404 = 2² × 101

Therefore, the HCF of these two integers is 2² = 4.

Also, LCM (96, 404) = \(% MathType!MTEF!2!1!+- % feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaSaaaeaaca % aI5aGaaGOnaiabgEna0kaaisdacaaIWaGaaGinaaqaaiaadIeacaWG % dbGaamOramaabmaabaGaaGyoaiaaiAdacaGGSaGaaGinaiaaicdaca % aI0aaacaGLOaGaayzkaaaaaiabg2da9maalaaabaGaaGyoaiaaiAda % cqGHxdaTcaaI0aGaaGimaiaaisdaaeaacaaI0aaaaiabg2da9iaaiM % dacaaI2aGaaGyoaiaaiAdaaaa!4FD8! \frac{{96 \times 404}}{{HCF\left( {96,404} \right)}} = \frac{{96 \times 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², 120 = 2³ × 3 × 5

Here, 2¹ and 3¹ are the smallest powers of the common factors 2 and 3, respectively.

So, HCF (6, 72, 120) = 2¹ × 3¹ = 2 × 3 = 6

2³, 3² and 5¹ 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² × 5¹ = 360

Remark : Notice, 6 × 72 × 120 \(% MathType!MTEF!2!1!+- % feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyiyIKlaaa!37BD! \ne \) 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.