# Complete induction proof that every $n > 1$ can be written as a product of primes

I'm trying to get through Spivak's Calculus on my own and even though I kinda understand induction I'm not so sure that's the case when it comes to complete induction. So I tried to do a starred problem which involves using it. But I'm not sure that my proof is valid, can someone check this for me?

So the problem is that I have to prove that

For every natural $n>1$, if $n$ is not prime we can write it as a product of primes.

I'm starting with a base case. For $n=2$, $n$ is prime, so the assumption holds.

Let's assume that for some $n > 1$ and also all numbers $p <= n$ the assumption holds.

Then $n+1 = cd$. If $n+1$ is not prime, then $c < n+1$ and $d < n+1$, but as they are natural numbers, we can also write that $c <= n$ and $d <= n$. But we assumed that if $p <= n$, and $p$ is not prime, we can write it as a product of primes. So if $c$ or $d$ are not primes, we can write them as a product of primes. That means that $n+1$ can be written as a product of primes if it's not prime, which completes the proof.

• It's the right idea, but not quite expressed correctly: what are $c,d$ supposed to be when first introduced? You should say that if $n+1$ is prime you're done, and if not you can factor it as $n+1=cd$ with $c,d<n+1$. Then you can apply the inductive hypothesis to $c$ and $d$. – Matthew Towers Jun 14 '14 at 10:31
• Further, it is more convenient to consider a prime as a product of primes (a product with one factor). Then every integer $> 1$ is a product of primes. – Bill Dubuque Jun 14 '14 at 14:35

For every natural $1<n<N$, if $n$ is not prime we can write it as a product of primes.
Let $N$ be composite, i.e. $N=a\cdot b$, with $1<a, b<N$.
Both $a$ and $b$ can be written either as a single prime or as a product of primes.
In any case, $N$ can be written as a product of primes, so that:
For every natural $1<n<N\color{red}{+1}$, if $n$ is not prime we can write it as a product of primes.
• I am afraid you did not handle the case that $c$ and $d$ are both primes. – Yves Daoust Jun 14 '14 at 10:33