Primes Archives - Stumbling Robot

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$

Stumbling Robot

Tag: Primes

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