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

*Proof.*The proof is by induction. If or , then is prime, so the statement is true.

Now assume that the statement is true for all integers from 2 up to . We want to show that this implies is either prime or a product of primes. If is prime then there is nothing to show and we are done. On the other hand, if is not prime, then we know there are integers and such that (i.e., is divisible by numbers other than 1 and itself).

By the induction hypothesis, since we know that and are either prime or are products of primes. But then and so is a product of primes (since the product is a product of primes, whether and are primes or products of primes themselves).

Hence, if the statement is true for all integers greater than 1 up to then it is also true for ; hence, it is true for all