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
Best Answer
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.