Home » Blog » Prove that every integer greater than 1 is a prime or is a product of primes

Prove that every integer greater than 1 is a prime or is a product of primes

Prove that every integer n > 1 is either prime or is a product of primes.


Proof. The proof is by induction. If n = 2 or n = 3, then n is prime, so the statement is true.
Now assume that the statement is true for all integers from 2 up to k. We want to show that this implies k+1 is either prime or a product of primes. If k+1 is prime then there is nothing to show and we are done. On the other hand, if k+1 is not prime, then we know there are integers c and d such that 1 < c,d < k+1 (i.e., n is divisible by numbers other than 1 and itself).
By the induction hypothesis, since 2 \leq c,d \leq k we know that c and d are either prime or are products of primes. But then k+1 = cd and so k+1 is a product of primes (since the product cd is a product of primes, whether c and d are primes or products of primes themselves).
Hence, if the statement is true for all integers greater than 1 up to k then it is also true for k+1; hence, it is true for all n \in \mathbb{Z}_{> 1}. \qquad \blacksquare

2 comments

  1. richardsull says:

    Apostol doesn’t address this kind of “strong” induction in the text, but I’m unaware of how to prove this with the “weak” version that he does provide. So this exercise feels a bit sneaky. It’s possible to prove a form of strong induction following a similar line of reasoning as the proof to Theorem I.36 (Princinple of Mathematical Induction).

Point out an error, ask a question, offer an alternative solution (to use Latex type [latexpage] at the top of your comment):