Question

Prove that any natural number greater than 1 is either prime or can be written as the product of primes

Answer 1

Answer:

Step-by-step explanation:

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