2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Matthew Towers Jun 14 '14 at 10:31
  • 2
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jun 14 '14 at 14:35
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hmmm, I understand that's one way we can prove it, but I'm still not sure whether my proof was valid or not. Can I get a clear answer to that question? $\endgroup$ – qiubit Jun 14 '14 at 10:31
  • $\begingroup$ I am afraid you did not handle the case that $c$ and $d$ are both primes. $\endgroup$ – Yves Daoust Jun 14 '14 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.