Using induction to prove all numbers are prime or a product of primes

Question

Let $n$ and $d$ denote integers. We say that $d$ is a divisor of $n$ if $n = cd$ for some integer $c$. An integer $n$ is called a prime if $n > 1$ and if the only positive divisors of $n$ are $1$ and $n$. Prove, by induction, that every integer $n > 1$ is either a prime or a product of primes.

My try: First, that there's nothing to prove because a number is always a prime or not, so do not what to think. Step: $P(n): n$ is either a prime or a product of primes. If n=2 then 2 is prime. $P(n): True$ I want to see $P(n) \rightarrow P(n+1)$ If $n$ is a prime then $2$ is a divisor of $p+1$, then is a product of primes. If $n$ is a product of primes... I can't say anything about $n+1$. Some help... please.

Answer 1

Strong induction:

Base case: $n=2$

$n$ has factors of 1,2 $n$ is prime:

Suppose for all $k\le n, k$ is either prime or can be represented as the product of a collection of prime factors.

We must show that either $n+1$ is prime or $n+1$ can be represented as the product of a collection of prime factors.

Suppose there are $2 \le c,d \le n$ such that $cd = n+1.$

In the case that n+1 is not prime. $c,d$ must either be prime or are the product of a set of prime factors. $cd$ is the product of prime factors.

If $c,d$ do not exist then $n+1$ is prime.

$n+1$ is either prime or the product of prime factors.

QED

Answer 2

Suppose that every integer $k$ such that $2\leq k\leq n$ is prime or a product of primes. This is the strong inductive hypothesis. You've already shown the base case. We show that $n+1$ is prime or a product of primes. If $n+1$ is prime we are done. Otherwise, write $n+1=ab$ where $2\leq a,b\leq n$ and use the inductive hypothesis.

Answer 3

This is a case where strong induction is needed, because a factorization of $n$ gives no information whatsoever on the factorization of $n+1$.

For the sake of brevity, I'll say that a number is a product of primes also when it is prime. Thus the statement is: “Every number $n\ge2$ is a product of primes”.

So the steps are

1. Prove the base case, here $n=2$

2. Prove that, if $n>2$ and every number $m$ with $2\le m<n$ is a product of primes, then also $n$ is a product of primes.

The base case is OK, as $2$ is prime.

Suppose $n>2$. If $n$ is prime, we're done. Otherwise $n=ab$, with $1<a<n$ and $1<b<n$. By the induction hypothesis, $a$ and $b$ are product of primes.