If $n$ is an integer with $n>1$, then $n$ has a prime factor. How do you do this using strong induction??
Asked
Active
Viewed 285 times
2
-
Have you even tried? – Parcly Taxel Oct 24 '16 at 03:01
-
You can't use the case $n=1$ so, yhe induction simple is not an option to show that, then use strong induction to show this for $n\geq 2$. – Ragnar1204 Oct 24 '16 at 03:02
-
I did that. how do I prove it using P(k+1)?? @Ragnar1204 – ash Oct 24 '16 at 03:09
-
6http://math.stackexchange.com/questions/934660/proof-that-every-number-has-at-least-one-prime-factor – Bram28 Oct 24 '16 at 03:23
1 Answers
1
Let $P(n)$ be "n has a prime factor". You need to prove "$P(2)$ is true" (Basis step) and "if $P(2)\land P(3)\cdots \land P(k)$ is true, then $P(k+1)$ is true" (Inductive step).
There are 2 case of $k+1$, prime or not prime. If it's prime then you are done. If it's not prime then exist $a,b$ such that $k+1=ab$. Since $2\le a \le b < k$, by inductive hypothesis $a,b$ both have prime factor. So $k+1=ab$ also have prime factor.