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?
Best Answer
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.