Proving the FTA

Number Theory · Axiom Academy

LESSON Proving the Fundamental Theorem of Arithmetic A complete proof with existence via strong induction and uniqueness via contradiction 1. Euclid's Lemma: The Foundation This lemma is essential for proving uniqueness. It tells us that primes behave "atomically" with respect to multiplication: they cannot divide a product without dividing at least one factor. 2. Existence: Every Number Has a Prime Factorization We prove existence using strong induction . The idea is simple: if a number is composite, we can split it into smaller factors, and by induction, those factors have prime factorizations. Base case: n = 2 is prime, so it is its own prime factorization. Inductive step: Assume every integer k with 2 k < n has a prime factorization. For n : If n is prime, it is its own prime factorization. If n is composite, then n = ab where 2 a, b < n . By the inductive hypothesis, both a and b have prime factorizations. Therefore, n = ab is the product of those prime factorizations. 3. Uniqueness: Setting Up the Contradiction To prove uniqueness, we assume the opposite: suppose some integer n has two different prime factorizations. We'll show this leads to a contradiction. Suppose n has two prime factorizations: Here, all p_i and q_j are primes. We assume these factorizations are different , meaning the multisets \ p_1, p_2, , p_r\ and \ q_1, q_2, , q_s\ are not identical. 4. Uniqueness: Applying Euclid's Lemma

This is the written version of the interactive lesson above. See the full Number Theory course.