Proof:Every natural number has a prime factorization

From CS2800 wiki

Here is a simplified version of the proof that every natural number has a prime factorization.

We use strong induction to avoid the notational overhead of strengthening the inductive hypothesis. This proof has the simplicity of the incorrect weak induction proof, but it actually works. You should compare the three versions of the proofs to understand the differences.

For all [math]n \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], if [math]n ≥ 2 [/math] then there exists prime numbers [math]a_0, a_1, \dots, a_k [/math] with [math]n = a_1 \cdot a_2 \cdots a_k [/math].
Proof: using strong induction
We will prove the claim using strong induction. Let [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n)} [/math] be the statement that "there exists prime numbers [math]a_0, a_1, \dots, a_i [/math] with [math]n = a_1 \cdot a_2 \cdots a_i [/math]. We will prove [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(2)} [/math] and [math]P(n) [/math] assuming [math]P(0), P(1), \dots, P(n-1) [/math].

In the base case, when [math]n = 2 [/math] we see that 2 is prime. Therefore, we can choose [math]a_0 = 2 [/math]; clearly [math]2 = 2 [/math].

For the inductive step, we assume [math]P(n-1), P(n-2), \dots, P(2) [/math] (or in other words, we strong induction [math]P(k) [/math] for all [math]k \lt n [/math]; our goal is to show [math]P(n) [/math], in other words that [math]n [/math] has a prime factorization.

There are two cases: [math]n [/math] could be prime or composite. If [math]n [/math] is prime, we can proceed as in the base case: simply choose [math]a_0 = n [/math].

If, on the other hand, [math]n [/math] is composite, then we know that [math]n = ab [/math] for some natural numbers [math]a [/math] and [math]b [/math].

Since [math]a [/math] and [math]b [/math] must be less than [math]n [/math], we can apply [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(a)} [/math] and [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(b)} [/math] to conclude that both [math]a [/math] and [math]b [/math] have prime factorizations.

Let [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(a_i)} [/math] be the prime factorization of [math]a [/math], and let [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(b_i)} [/math] be the prime factorization of [math]b [/math]. If we let [math](c_i) [/math] be the sequence starting with the [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(a_i)} [/math] and ending with the [math]\href{/cs2800/wiki/index.php/Sequence_notation}{b_i} [/math]s (in other words, [math]c_0, c_1, \dots = a_0,a_1,\dots,a_p,b_0, b_1, \dots, b_q [/math]). Then clearly [math]n = \prod c_i [/math].