Consider the following theorem.
Theorem 17a (6.4: Exercise 17a): For positive integers a and b and all primes p, if p|ab, then either p|a or p|b.
We shall use Theorem 17a to prove the following theorem.
Theorem 17b (6.4: Exercise 17b): For all positive integers n, for all primes p, if p divides the product of n positive integers, then p divides one of the factors.
Proof: (by induction) For all positive integers n, let P(n) be the statement “for all primes p, if p divides the product of n positive integers, then p divides one of the factors”.
Induction step: (∀ n ∈ Z+) ([(∀ k ∈ Z+)(k < n → P(k)] → P(n)).
Let m ∈ Z+ be arbitrary.
Assume for all positive integers k that k 1. For concreteness, let a = (a_1)(a_2)…(a_{m-1})(a_m) be the product of m factors that p divides. Since a = [(a_1)(a_2)…(a _{m-1})][a_m] and p divides a, by Theorem 17a, either p|[(a _1)(a _2)…(a _{m-1})] or p|a_m.
Subcase 2a: p|a_m
In this case, p divides one of the factors, namely a_m.
Subcase 2b: p|[(a_1)(a_2)…(a_{m-1})]
Apply the induction hypothesis with k=m-1 to see that p divides one of a_1,…,a_{m-1}, so it divides one of the factors of a.
By subcase analysis, in case 2, p divides one of the factors, since it does in both subcases and one of the subcase 2a and subcase 2b must hold.
Thus by case analysis, p divides one of the factors of a, since it does in both cases and one of the case 1 and case 2 must hold.
We assumed p divides the product a of m positive integers, and proved p divides one of the factors, so the implication follows. Since p was an arbitrary prime, true for all such, so P(m) is true.
We assumed for all positive k that k < m implies P(k) and proved P(m), so the implication follows.
Since m ∈ Z+ was arbitrary, true for all such. Thus the induction step is complete.
Therefore, by strong induction, for all n ∈ Z+, P(n) is true, and the theorem follows.