A proof that every integer greater than 1 is a product of primes

Question

In my calculus textbook we are asked to prove that every integer greater than 1 is a product of primes. This theorem is not new to me, however, the proof they provide seems unnecessarily long.

Proof: The induction step holds because 2 is prime and thus also a product of primes. Let's assume that every number in the set $2,3,4,...,n$ is a product of primes and we want to prove that $n+1$ is also a product of primes. Let $p$ be the smallest number from $2,3,4,...,n,n+1$ that divides $n+1$. We see that $p$ is prime, because if it's not there exists a $d$ such that $2 \le d<p$ that divides $p$ and also divides $n+1$ but $p$ is minimal a contradiction, therefore $p$ is prime. If $p=n+1$ then $n+1$ is prime and we are done. Else, $p<n+1$, and $q=(n+1)/p$ is bigger than 1 and smaller than $n+1$, and therefore from the induction hypotheses $q$ is the product of primes. Thus, $n+1=pq$ is also a product of primes.

I don't understand why $p$ needs to be prime. Shouldn't it be enough to know that $p$ is a product of primes and then we just get to the conclusion much faster?

Answer 1

Yes, if the least factor $\,p>1\,$ of $\,n\!+\!1$ is $\rm\color{#c00}{smaller}$ $(p < n\!+\!1)$ we do not need to prove $\,p\,$ is prime, since then ${\rm\color{#c00}{induction}}\Rightarrow p$ is a product of primes. But if $\,p = n\!+\!1\,$ then induction does not apply so then we need to use the knowledge that $\,p\,$ is prime to conclude the proof.

We can elmininate this inelegant exceptional case by instead basing the induction not at $\,n=2\,$ but instead at $\,n=1,\,$ viewing $1$ as an empty product of primes. Now the inductive step works smoothly: $ $ the least factor $\,p>1\,$ of $\,n\!+\!1\,$ is prime (as they proved) and $\,(n\!+\!1)/p < n\!+\!1,\,$ so induction $\Rightarrow (n\!+\!1)/p\,$ is a product of primes (possibly empty), so appending '$p$' to this product yields a prime factorization of $\,p(n\!+\!1)/p = n\!+\!1,\,$ completing the induction.

---

More generally and naturally: a simple induction shows that if a set of positive naturals contains $1$ and all primes and is closed under multiplication, then it is the set of all positive naturals. But the set of positive naturals writable as prime products clearly satsifies all those hypotheses, hence it is includes every positive natural.

This method of proof is more faithful to the (algebraic) structural heart of the matter - that the multiplicative monoid of positive naturals is (freely) generated by the primes, so that above method of induction is the natural structural induction to apply in multiplicative contexts (i.e. induction proofs "piggyback" on the inductive geenration of the structure). Follow the prior link for much further discussion.

Answer 2

Staying with the method used, during the strong-induction hypothesis, every integer $k$ such that $~2 \leq k \leq n~$ is a product of primes. This does not immediately imply that $(n+1)$ is a product of primes.

If $p$ is the smallest number that divides $(n+1)$, and $p$ happens to be less than $(n+1)$, then you can conclude that both $p$ and $~\dfrac{n+1}{p}~$ are the product of primes.

However, you could have that $p = (n+1),$ rather than $p < (n+1).$ In this situation, the analysis in the previous paragraph does not hold, so you can not then immediately conclude that $(n+1)$ is the product of primes.

It is only after concluding that in this exceptional case, that $p = (n+1)$ must therefore be prime, and thus the product of primes, can you construe that the strong-induction hypothesis step has been completed.