Prime Factorization: The Fundamental Theorem of Arithmetic

Hello! In our last lesson, we mastered Euclid's division algorithm, a systematic process for finding the HCF of two integers. This algorithmic approach provided an efficient alternative to simply listing factors. Today, we delve into another foundational concept of number theory: the Fundamental Theorem of Arithmetic.

This theorem reveals a deep and elegant truth about the structure of numbers. It essentially states that prime numbers are the fundamental "building blocks" of all whole numbers. Our goal today is to understand this theorem, appreciate its significance, and apply it to break down any composite number into its unique prime factors—a process known as prime factorization. This skill will not only deepen your conceptual understanding but also serve as the basis for our next topic: finding HCF and LCM using a new method.

The Atoms of Numbers: What the Theorem States

The Fundamental Theorem of Arithmetic is one of those beautifully simple yet profound ideas in mathematics. It asserts that every composite number can be written as a product of prime numbers, and that this representation is unique, apart from the order in which the prime factors are listed.

Let's start with a formal definition and a clear example.

Fundamental Theorem of Arithmetic - Statement, Proof, Examples

This article from Cuemath gives a direct statement of the theorem and illustrates it with an example.

Please read the section Fundamental Theorem of Arithmetic Definition. Then, look at the last FAQ for another simple case: Explain the Fundamental Theorem of Arithmetic with an Example?.

As the resource explains, the theorem has two key parts:

Existence: Any composite number can be factored into a product of primes.
Uniqueness: This set of prime factors is unique for every number.

Think of prime numbers as the atoms of the number world. Composite numbers are the molecules they form. For example, the number 12 is a "molecule" that is always composed of two 'atoms' of prime 2 and one 'atom' of prime 3. We can write this as $12 = 2 \times 2 \times 3$ , or $12 = 2 \times 3 \times 2$ , but the fundamental components—the set of prime factors {2, 2, 3}—are always the same. No other combination of primes will multiply to give 12. This uniqueness is the core power of the theorem.

How to Find the Prime Factors

Now that we know every composite number has a unique prime factorization, how do we find it? There are two common methods.

The Division Method: This is a systematic approach where you repeatedly divide by the smallest possible prime numbers.
The Factor Tree Method: This is a more visual approach where you branch out factors until you are left with only primes.

The image below demonstrates both methods for finding the prime factorization of 40.

This image from Cuemath shows two methods for finding the prime factorization of 40. The division method (left) involves sequential division by primes. The factor tree method (right) involves branching factors until all branches end in a prime. Both yield the same unique factorization: $2^3 \times 5$.

To see the division method applied to more complex numbers, the following video provides excellent step-by-step demonstrations.

The Fundamental Theorem of Arithmetic - Real Numbers | Class 10 Maths Chapter 1 | CBSE 2025-26

This video from Magnet Brains walks through the process of prime factorization for several numbers, which will help solidify the practical application of the theorem.

Watch the segment from this timestamp. It demonstrates the division method for three numbers: 140, 3825, and the more challenging 7429. Notice how the process is the same regardless of the number's size.

The process is essentially an algorithm:

Start with the given composite number.
Divide it by the smallest prime number that divides it evenly (start with 2, then 3, 5, etc.).
Take the result (the quotient) and repeat the process.
Continue until the quotient is 1.
The prime factorization is the product of all the prime divisors you used.

Check Your Understanding

Try finding the prime factorization of 156 using either the division method or a factor tree.

Click to see the solution

Using the division method:

$156 \div 2 = 78$
$78 \div 2 = 39$
$39 \div 3 = 13$
$13 \div 13 = 1$

The prime factors are 2, 2, 3, and 13. So, the prime factorization of 156 is $2^{2} \times 3 \times 13$ .

The Proof: Why Is the Factorization Unique?

Your preference for understanding the "why" behind concepts is particularly relevant here. The uniqueness of prime factorization is not immediately obvious and requires a formal proof. The argument is elegant and often uses proof by contradiction, a common technique in both mathematics and formal logic in computer science.

The following video provides a very clear and intuitive walkthrough of this proof.

The Fundamental Theorem of Arithmetic

This video from Dr. Will Wood explains the proof of uniqueness in a logical, step-by-step manner.

Watch the section from here. The presenter starts by assuming a number could have two different prime factorizations and then shows how this leads to a logical contradiction.

To summarize the logic of the proof:

Assumption: Assume there exists a number, let's call it $n$ , that has two different prime factorizations. Let's say $n = p_{1} \times p_{2} \times \dots$ and also $n = q_{1} \times q_{2} \times \dots$ , where the set of $p$ primes is different from the set of $q$ primes.
The Key Property: We rely on a property derived from Euclid's work: if a prime number (say, $p_{1}$ ) divides a product of other numbers, it must be equal to one of those numbers.
The Contradiction: Since $p_{1}$ is a factor of $n$ , it must also divide the other factorization ( $q_{1} \times q_{2} \times \dots$ ). According to the property above, $p_{1}$ must be equal to one of the $q$ primes. We can then cancel this common prime from both factorizations. By repeating this process for all the $p$ primes, we find that the two sets of factors must have been identical to begin with. This contradicts our initial assumption that they were different.
Conclusion: Therefore, the prime factorization of any number must be unique.

For a more formal, text-based proof that explicitly references Euclid's Lemma from our previous lessons, you can review the following.

Fundamental Theorem of Arithmetic Proof & Solved Examples

This article from Testbook presents the formal proof in two steps: existence and uniqueness.

Read the section Fundamental Theorem of Arithmetic Proof. Pay attention to "Step 2", which proves the uniqueness and explicitly uses Euclid's lemma.

An Application: A Classic Problem

The uniqueness property of prime factorization is a powerful tool for solving certain types of number theory problems. Consider this question: "Can a number of the form $4^{n}$ , where $n$ is any natural number, ever end with the digit 0?"

We can answer this with the Fundamental Theorem of Arithmetic.

A number ends with the digit 0 only if it is divisible by 10.
For a number to be divisible by 10, its prime factorization must contain both a 2 and a 5.
Let's look at the prime factorization of $4^{n}$ . The number 4 is $2^{2}$ .
Therefore, $4^{n} = (2^{2})^{n} = 2^{2 n}$ .
According to the Fundamental Theorem of Arithmetic, the prime factorization of any power of 4 will only contain the prime number 2. It will never contain the prime 5.
Since the prime factor 5 is always missing, no number of the form $4^{n}$ can be divisible by 10. Thus, it can never end with the digit 0.

This shows how the theorem provides a definitive and rigorous way to prove properties about numbers.

Conclusion

In this lesson, we explored the Fundamental Theorem of Arithmetic, which states that every composite number can be broken down into a unique product of prime numbers. This gives us a powerful lens through which to view the integers.

Key Takeaways:

The Theorem: Every composite number can be factorized as a product of primes, and this factorization is unique (apart from the order of factors).
Prime Factorization: We can find this unique set of prime factors using methods like the division method or factor trees.
Uniqueness is Key: The uniqueness of prime factors is a powerful property that allows us to prove other facts about numbers, such as why $4^{n}$ can never end in zero.

We've now seen two pillars of number theory: Euclid's algorithm and the Fundamental Theorem of Arithmetic. In our next lesson, we will use prime factorization to develop a powerful and intuitive method for finding both the Highest Common Factor (HCF) and the Lowest Common Multiple (LCM) of integers.