Uniqueness of Prime Factorization: Exploring the Fundamental Theorem of Arithmetic

Introduction

The Fundamental Theorem of Arithmetic is a foundational concept in number theory. It asserts that every integer greater than 1 can be uniquely expressed as a product of prime numbers. In this article, we will delve into the proof of this theorem, highlighting both the existence and uniqueness aspects.

Proof Outline

Existence of Prime Factorization

The proof of the Fundamental Theorem of Arithmetic is divided into two main parts: existence and uniqueness. Here, we will explore the existence aspect.

Base Case

For the smallest integer n 2, which is a prime number, the factorization is simply 2.

Induction Hypothesis and Step

Assume that every integer k, where 2 ≤ k ≤ n, can be expressed as a product of primes. We need to show that n 1 can also be factored into primes.

If n 1 is prime, then it is its own prime factorization. Otherwise, n 1 is composite and can be expressed as a × b, where 2 ≤ a ≤ b ≤ n. By the induction hypothesis, both a and b can be factored into primes. Thus, n 1 can also be expressed as a product of these primes.

By induction, every integer greater than 1 can be factored into primes.

Uniqueness of Prime Factorization

After establishing the existence, we need to prove that the factorization is unique.

Proof of Uniqueness

Assume that an integer n 1 can be expressed as two different products of primes:

n 1 p1 × p2 × ... × pk q1 × q2 × ... × qm

Here, pi and qj are primes.

Consider the smallest prime in the factorization, p1. Since p1 divides n 1, it must also divide the product on the right side:

p1 ∣ q1 × q2 × ... × qm

By the property of primes, a prime divides a product if and only if it divides at least one of the factors. Therefore, p1 must divide at least one of the qj. Let’s say p1 qk for some k.

Cancelling p1 from both sides, we get:

(n 1)/p1 p2 × ... × pk q1 × ... × qk-1 × qk 1 × ... × qm

This new product is a factorization of (n 1)/p1, which is less than n 1. By the induction hypothesis or by the same argument, this factorization must also be unique.

Continuing this process shows that all primes pi must be equal to some qj, and thus establishes that the original factorizations must include the same primes with the same multiplicities.

Conclusion

Therefore, we conclude that every integer greater than 1 has a unique prime factorization, completing the proof of the Fundamental Theorem of Arithmetic.