Course contentsShow
← Mathematics
Lesson 2726 of 3,12154. Number TheoryFree lesson

Uniqueness of Prime Factorization: The Proof

Explore the proof of uniqueness using mathematical induction and properties of divisibility by primes.

Uniqueness of Prime Factorization: The Proof

What you'll learn: You'll understand the rigorous proof that every integer greater than 1 has exactly one prime factorization (up to order).

Why Uniqueness Matters

You've seen that every integer greater than 1 can be written as a product of primes. But could there be two different ways to do this? For example, could 30 = 2 × 3 × 5 and also equal some completely different prime product? The Fundamental Theorem of Arithmetic guarantees this never happens—and we prove it using a technique called proof by contradiction combined with properties of divisibility.

The Proof Structure

Setup: Assume for contradiction that some integer n has two distinct prime factorizations:

n = p₁ × p₂ × ... × pᵣ = q₁ × q₂ × ... × qₛ

where all p's and q's are primes, and these lists are genuinely different (not just reordered).

Key step using prime divisibility: Since p₁ divides n, and n equals the product q₁ × q₂ × ... × qₛ, we know p₁ divides this entire product. A crucial property of primes (proven using Bézout's Identity and the Euclidean Algorithm) says: if a prime divides a product, it must divide at least one factor. So p₁ must equal some qⱼ.

The contradiction: Cancel p₁ from both sides. Repeat this process for each prime. Eventually, you'll exhaust one factorization while the other still has primes left—meaning 1 equals a product of primes, which is impossible. This contradiction proves our assumption was wrong: there can't be two distinct factorizations.

Key Takeaway: The uniqueness of prime factorization is guaranteed by the fundamental divisibility property of primes—if a prime divides a product, it must divide one of the factors—combined with proof by contradiction to show no integer can have multiple distinct prime decompositions.