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.