Proving Every Integer > 1 Has Prime Factorization

Intro to Proofs · Axiom Academy

EXAMPLE Prime Factorization Existence Proof Understanding why strong induction is necessary for proving the Fundamental Theorem of Arithmetic Excellent work! You've understood why strong induction is essential for this proof. Here's what we learned: Weak vs Strong Induction: Weak induction only assumes P(n-1), while strong induction assumes P(k) for all k < n. This makes strong induction more powerful. When to Use Strong Induction: Use strong induction when the inductive step requires information about multiple previous cases, not just the immediate predecessor. The Factorization Problem: When n = ab with a, b > 1, we can't guarantee a = n-1 or b = n-1. Both factors could be much smaller, so we need strong induction to use P(a) and P(b). Two Cases for n: The inductive step naturally splits into n being prime (trivial) or composite (apply hypothesis to factors). Building Up Factorizations: By knowing all smaller numbers have prime factorizations, we can combine them to show n does too. This proof demonstrates the existence part of the Fundamental Theorem of Arithmetic. The uniqueness part (up to reordering) requires additional work, but existence alone is a powerful result that relies crucially on strong induction!

This is the written version of the interactive lesson above. See the full Intro to Proofs course.