# Prove by induction that every integer is either a prime or product of primes

Let $n$ and $d$ be integers such that $d$ is a divisor of $n$ if $n=ad$ for some integer $a$. A prime number is a integer $n>1$ that is divisible by 1 and itself. Prove by induction that every integer $n>1$ is either a prime or product of primes.

My attempt:

Proving equation is true for a particular $n$

If $n=2$ then $n=2=2\cdot 1=1\cdot 2=ad$ , $d$=1,2 then $n$ its a prime since a prime is greater than 1.

If $n=4$ them $n=4=2\cdot 2\cdot 1=1\cdot 2\cdot 2=ad$ , $d$=1,2 then its a product of primes namely $n=2\cdot 2$.

is this ok ?

now assuming $n$ is true lets prove $n+1$

$n=ad$

$n+1=ad+1$

If its prime then...

If it is a product of primes then...

I don't know how to continue

I have seen this however i don't know if it is a good answer however I find it incomplete

• Try to complete the answer you have cited here. – Dietrich Burde May 14 '15 at 18:35
• – Dr. Sonnhard Graubner May 14 '15 at 18:36
• This sentence "if $n=2$ then $n=2=2\cdot 1=1\cdot 2=ad$ , $d$=1,2 them $n$ its a prime since a prime is greatter than 1" is very bad English. First off, I noticed you wrote "them" every time you meant "then" (I fixed most of them). You should take your time and formulate your sentences carefully. – Gregory Grant May 14 '15 at 18:38
• yes , i have make some mistakes – user238670 May 14 '15 at 18:41
• how i complete the answer by editing the answer there? @DietrichBurde – user238670 May 14 '15 at 18:42

You will need strong induction, so you assume it holds for all $n < N$.

Then you prove it for $n=N$.

For $n=2$ it clearly holds.

Now assume it holds for all $n < N$.

If $N$ is a prime, then the statement is true.

Else, you can write $N = a\cdot b$ with $a,b < N$, and by the strong induction hypothesis you can write $a,b$ as a prime or a product of primes, so $N$ is a product of primes.

• is in my attempt the prove that n=2 holds ok? – user238670 May 14 '15 at 18:48
• No, not really, you can just say that n=2 is prime and be done with it. – wythagoras May 14 '15 at 18:49
• strong induction is when using inequalities? – user238670 May 14 '15 at 18:52
• I don't really understand the question, but strong induction is used when you not only assume the previous value, but all previous values. – wythagoras May 14 '15 at 18:58
• ok now i understand what you mean by strong induction, thanks – user238670 May 14 '15 at 18:59