Fundamental Theorem of Arithmetic: Proof and Examples

The fundamental theorem of arithmetic, also called the unique factorization theorem, falls in a branch of mathematics called number theory. It states that every composite number can be factored in as a product of primes in a unique method, apart from the primes’ order. That is, given any composite number, there is only one method to write it as a product of primes if neglecting the order in which these primes appear. As a result, we consider the product of primes \(2 \times 3 \times 5 \times 7\) to be the same as \(3 \times 5 \times 7 \times 2\), or any other such order. This article elaborates the fundamental theorem of arithmetic with its proof and solved examples.

Fundamental Theorem of Arithmetic

To understand fundamental theorem of arithmetic better, let us consider the prime factorization of 240.

Upon factorising 240, we get 240 = 2 × 2 × 2 × 2 × 3 × 5

This prime factorization can also be written as: 240 = 3¹ × 2⁴ × 5¹

The Fundamental Theorem of Arithmetic theorem says two things about this example: first, that 240 can be represented as a product of primes, and second, that no matter how this is done, there will always be exactly four 2s, one 3, one 5, and no other primes in the product.

Prime Factorisation

The term prime factorisation refers to representing a number as a product of prime numbers.
Prime factorisation of \(18\) for example, is the representation of \(18\) as a product of prime numbers and can be done as follows:

Prime factorisation of \(18 = 2 \times 3 \times 3 = 2 \times {3^2}\)

Here \(2\) and \(3\) are prime numbers.

Definition of Fundamental Theorem of Arithmetic

The statement of fundamental theorem of arithmetic is: Every natural number except \(1\) can be factorized as a product of primes, and this factorisation is unique except for the order in which the prime factors are written. According to the fundamental theorem, every composite number can be uniquely decomposed as a product of prime numbers. In the sense that the decomposition can only be expressed as a product of primes in one way.

In general, we find that if we have a composite number \(N\), we can decompose it uniquely in the form

\(N = {p_1}^{{q_1}} \times {p_3}^{{q_2}} \times {p_3}^{{q_3}} \times {p_4}^{{q_4}}… \times {p_n}^{{q_n}}\)

where \({p_1},{p_2},{p_3},{p_4}…\,,{p_n}\) are primes and \({q_1},{q_2},{q_3},{q_4}…\,,{q_n}\)are natural numbers.

First, we try to factorize \(N\) into its factors. If all the factors are primes, then we can stop. Otherwise, we try to split further the factors which are not prime and continue the process till we get only prime numbers.

Proof of Fundamental Theorem of Arithmetic

We must prove the prime factorisation’s existence and uniqueness to prove the fundamental theorem of arithmetic. As a result, the fundamental theorem of arithmetic states that proof takes \(2\) steps.

We will show that for every integer, \(n \ge 2,\) the product of primes can be written in only one way:

\(n = {p_1}.{p_2}\,…{p_i}\)

Step \(1\): Determine whether prime factorisation exists.

Mathematical induction will be used to demonstrate this. Mathematical induction is a technique used to prove that a statement, a formula, or a theorem is true for every natural number.

The technique involves two steps to prove a statement, as stated below −

Base step − It proves that a statement is true for the initial value.

Inductive step − It proves that if the statement is true for the \({n^{th}}\)  iteration (or number \(n\) then it is also true for \({(n + 1)^{th}}\) iteration (or number \((n + 1)\)).

\(i\) (Base step): For \(n = 2\) the assertion is correct.

\(ii\) (Inductive step): Assume the assertion is correct for \(n = k\).

The product of primes can thus be written as \(k\). Let us prove that the statement is correct for \(n = k + 1\)

The case is evident if \(k + 1\) is prime.

If \(k + 1\) not prime, it almost certainly has a prime factor, such as \(p\). Then \(k + 1 = {p_j}\) where \(j < k \to (1)\)

Since \(j < k,k\) can be represented as the product of primes using the inductive step. As a result of \((1),k + 1\) can also be expressed as a prime product. The presence of factorisation is thus proven through mathematical induction.

Step \(2\): Prime factorisation’s uniqueness

Assume that \(n\) can be expressed in two ways as the product of primes, for example,
\(n\, = \,{p_1}{p_2}\,…{p_i}\)
\( = {q_1}{q_2}\,…{q_j}\)
\({q_1}{q_2}\,…{q_j}\) are coprime numbers since these are prime factorisations (as they are prime numbers).

As a result, Euclid’s Lemma states that \({p_1}\) divides only one of the primes.

\({p_1} = {q_1}\) because \({q_1}\) is the smallest prime.

Similarly, we may prove that \({p_n} = {q_n}\)  for all \(n\). As a result, \(i = j\)

As a result, \(n’\) prime factorisation is unique.

The following simulation can be used to find the prime factorisation of any number.

Example of Fundamental Theorem of Arithmetic

Let us look at the prime factorisation of \(240\)

From the above figure,

\(240 = 2 \times 2 \times 2 \times 2 \times 3 \times 5 = {2^4} \times 3 \times 5 = {2^4} \times 3 \times 5 = {2^4} \times {3^1} \times {5^1}\)

Our theorem also states that this factorisation must be unique. In other words, there is no alternative method to describe \(240\) as a prime product. Of course, the order in which the prime factors appear can be altered. The prime factorisation, for example, can be represented as

\(240 = {3^1} \times {5^1} \times {2^4} = {3^1} \times {5^1} \times {2^2} \times {2^2}\)

However, the set of prime factors and the frequency with which each factor appears are unique. That is, with four factors of \(2\), one factor of \(3\), and one factor of \(5,\,240\) can only have one prime factorisation.

HCF and LCM Using Fundamental Theorem of Arithmetic

The fundamental theorem of arithmetic is used to compute the HCF and LCM of two numbers. We start by determining the prime factorisation of both numbers. After that, we will have a look at the following:

1. HCF of two or more numbers is the smallest power of each common prime factor in the numbers.
2. LCM of two or more numbers is the product of the greatest power of each common prime factor in the numbers.

Example: Find the HCF of \(850\) and \(680\) using the prime factorisation method?

We first find the prime factorisations of these numbers.

Thus : \(850 = {2^1} \times {5^2} \times {17^1}\)
\(680 = {2^3} \times {5^1} \times {17^1}\)

HCF is the product of the smallest power of each common prime factor.
Hence, HCF \((850,680) = {2^1} \times {5^1} \times {17^1} = 170\)

LCM is the product of the greatest power of each common prime factor.
Hence, \({\rm{LCM}}(850,680) = {2^3} \times {5^2} \times {17^1} = 3400\)

Thus, \({\rm{HCF(850,680)}}\,{\rm{ = }}\,{\rm{170}}\)
\({\rm{LCM}}\,{\rm{(850,680)}}\,{\rm{ = }}\,3400\)

Significance of Fundamental Theorem of Arithmetic

The above-mentioned fundamental theorem concerning natural numbers except \(1\) has various applications in mathematics and other subjects. The theorem is significant in mathematics because it emphasizes that prime numbers are the building blocks for all positive integers. Prime numbers can thus be compared to the atoms that make up a molecule.

1. If a prime number \(p\) divides \(ab,\) it divides either \(a\,or\,b,\) implying that \(p\) divides at least one of them.
2. If a composite number \(n\) divides \(ab,\)\(n\) divides neither \(a\,nor\,b\) For example, \(6\)
3. divides \(4 \times 3\) but does not divide \(4\, or 3\).

Solved Examples – Fundamental Theorem of Arithmetic

Let us understand the facts of the fundamental theorem of arithmetic through some solved examples.

Q.1. Express \(1080\) as the product of prime factors. Is this factorisation unique?
Ans: Let us find the prime factorisation of \(1080\)

Thus, \(1080 = {2^3} \times {3^3} \times {5^1}\)
The above prime factorisation is unique by the fundamental theorem of arithmetic.

Q.2. Find the HCF of \(126,162\) and \(180\) by using the fundamental theorem of arithmetic.
Ans: Let us find the prime factorisations of \(126,162,\,and\,180\)

Thus, \(126, = 2 \times 3 \times 3 \times 7 = {2^1} \times {3^2} \times {7^1}\)
\(162 = 2 \times 3 \times 3 \times 3 \times 3 = {2^1} \times {3^4}\)
\(180 = 2 \times 2 \times 3 \times 3 \times 5 = {2^2} \times {3^2} \times {5^1}\)
The HCF of two or more numbers is the smallest power of each common prime factor in the numbers.
Hence, \({\rm{HCF(126,162,180) = }}{{\rm{2}}^1} \times {3^2} = 18\)

Q.3. Find the LCM of  \(48\) and \(72\) by using the fundamental theorem of arithmetic.
Ans: Let us find the prime factorisations of \(48\) and \(72\).

Thus, \(48 = 2 \times 2 \times 2 \times 2 \times 3 = {2^4} \times {3^1}\)
\(72 = 2 \times 2 \times 2 \times 3 \times 3 = {2^3} \times {3^2}\)
The LCM of two or more numbers is the product of the greatest power of each common prime factor in the numbers.
Hence, \({\rm{LCM}}(48,72) = 2 \times 2 \times 2 \times 2 \times 3 \times 3 = {2^4} \times {3^2} = 144\)

Q.4. In the given factorisation, find the numbers \(m\) and \(n\)

Ans: Let us start the calculation from the bottom.
The value of the first box from bottom \( = 5 \times 2 = 10\)
Value of \(n = 5 \times 10 = 50\)
Value of the second box from bottom \( = 3 \times 50 = 150\)
Value of \(m = 2 \times 150 = 300\)
Thus, the required numbers are \(m = 300,\,n\, = \,50\)

Q.5. Given \(a\) and \(b\) are two positive integers such that \({a^b} \times {b^a} = 800\) Find \(a\) and \(b\).
Ans: The number \(800\) can be factorized as
\(800 = 2 \times 2 \times 2 \times 2 \times 2 \times 5 \times 5 = {2^5} \times {5^2}\)
Hence, \({a^b} \times {b^a} = {2^5} \times {5^2}\)
This implies that \(a = 2\,and\,b = 5\,(or)\,a = 5\,and\,b = 2\)

Summary

In this article, we talked about how to perform prime factorisation and understood the fundamental theorem of arithmetic. Also, we proved the theorem in a two-step method and, through some examples, learnt how to obtain the HCF and LCM using the fundamental theorem of arithmetic. The article also explored the relevance of the fundamental theorem of arithmetic.

The concept of the fundamental theorem of arithmetic can be easily understood with the help of solved instances.

Frequently Asked Questions (FAQs) – Fundamental Theorem of Arithmetic

We have answered the most commonly asked questions about the Fundamental Theorem of Arithmetic here:

We hope this detailed article on the fundamental theorem of arithmetic helped you in your studies. If you have any doubts or queries on this topic, feel to ask us in the comment section.