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

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