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 = 11 × 23. 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 .

What about 1771? 1771=

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.

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 intersting conclusions.

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

Solution : If the number 4n, 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 4n would contain the prime 5. This is not possible because 4n=22n; so the only prime in the factorisation of 4n is 2. So, the uniqueness of the Fundamental Theorem of Arithmetic guarantees that there are noother primes in the factorisation of 4n . So, there is no natural number n for which 4n ends with the digit zero.

So we took the uniqueness part of the theorem and applied it to quickly deduct the point that 4n will never end with zero for all n belongs to natural numbers.

HCF and LCM

We have already learnt how to find HCF and LCM earlier. The prime factorization method actually uses the Fundamental Theorem of Arithmetic to gets its result. Let us quick;y revisit with an example.

Find the HCF and LCM of 6 and 20.

Solution:

Prime factors of 6=*.

6= 21·3

Prime factors of 20=***

20= 22·5

So HCF(6,20)= and LCM(6,20)=

HCF(6, 20) = 21 = Product of the smallest power of each common prime factor in the numbers.

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

In the example above we can see that HCF(6, 20) × LCM(6, 20) = 2*60=120.

But 6*20 is also equal to 120.

In fact, it can be proven that for any a,b, HCF(a,b)LCM(a,b)=ab. This will easily enable us to find the HCF or the LCM if the other is given.