# Fundamental Theorem of Arithmetic: Proof and Examples

The Fundamental Theorem of Arithmetic
The Fundamental Theorem of Arithmetic

Nuclear Fission and Fusion: What is the source of this huge amount of energy emitted by the sun and the stars? The answer to this…

Nuclear Fission and Fusion: Definition, Applications, Types and Examples

August 21, 2023

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.

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 = 31 × 24 × 51

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.

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.

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.

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.

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.

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:

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$$

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.

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$$

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.

 Q.1. What is the fundamental theorem of arithmetic, and why is it important? Ans: The fundamental theorem of arithmetic states that: 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. The existence and uniqueness of the prime factorisation of a number, which is employed in obtaining the HCF and LCM, are guaranteed by the fundamental theorem of arithmetic.
 Q.2. How do you prove the fundamental theorem of arithmetic? Ans: We must prove the prime factorisation’s existence and uniqueness to prove the fundamental theorem of arithmetic.
 Q.3. Who found the fundamental theorem of arithmetic? Ans: Carl Friedrich Gauss proved the fundamental principle of number theory in $$1801$$. The theory claims that there is only one way to express any integer bigger than $$1$$, i.e., as the product of prime numbers.
 Q.4. What does the theorem say about the product of primes? Ans: Every composite number can be factored in as a product of primes, according to the Fundamental Theorem of Arithmetic. It claims that any composite number may be factored in as a product of prime numbers in a unique method, apart from the order of primes. For this example, the theorem states that $$1200$$ may be expressed as a product of primes and that no matter how this is done, the product will always contain exactly four $$2s,$$ one $$3$$,two $$2s,$$ and no other primes. $$1200 = {2^2} \times 3 \times {5^2} = {2^4} \times {5^2} \times 3$$
 Q.5. How to find HCF using the fundamental theorem of arithmetic? Ans: The fundamental theorem of arithmetic is used to compute the HCF of two or more numbers. We start by determining the prime factorisation of two or more numbers. HCF is the product of the smallest power of each common prime factor. For example, HCF of $$680$$ and $$850$$ is given by $$850 = {2^1} \times {5^2} \times {17^1}$$ $$680 = {2^3} \times {5^1} \times {17^1}$$ Hence, HCF $$(850,680) = {2^1} \times {5^1} \times {17^1} = 170$$

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 free to ask us in the comment section.

Practice Arithmetic Questions with Hints & Solutions