Using Strong Induction

Question

The statement is: If $n$ is an integer with $n > 1$, then $n$ has a prime factor. I know you have to use $P(k+1)$ but I'm not sure how to implement that into the proof. Is this even going in the right direction?

Answer 1

This is a perfect example of strong vs. weak induction. We don't care in the slightest bit that $n+1$ is the number immediately after $n$. We care only that $n+1$ is larger than $1....n$.

Base case: $n =2$. $n = 2 $ has a prime factor because $2$ itself is prime.

Induction step: Assume that every number from $2....n$ have prime factors.

$n+1$ has factors. Because all numbers have factors. $n+1$ has $1$ and $n+1$ as factors. Does it have any others?

If not, then $n+1$ is prime and that is a prime factor.

Otherwise if $n+1$ has a factor $k$, $k \ne 1; k \ne n+1$ where $k|n+1$....

Well, here are some questions for you:

Is $k > n+1$?

If not then ... what is it compared to $n+1$? ..... So what else can we assume about $k$? ... because we are doing strong induction so we are making an assumption of what...?

So what does that tell us about $n+1$?

====

The trick is on weak induction we would assume the property is true for $n$ to get that it is true for $n+1$.

In this strong induction we are not doing that. We are assuming it is true on some $k$ that is not $n$ and using that it is true on $k$, and therefore it is true on $n+1$. We are using i) $k|n+1$ and $k < n+1$. The number $n$... is completely off the table and has nothing to do with anything.

Answer 2

In order for you to have a n value with prime factorization, n must be greater than 1 (given). Therefore our base case would be n=1 for n in natural numbers. We thus need an equation that validates n has prime factors, such as 2^n = k for some integer k.
K=2 for n=1. This would validate there are prime factors since 2 is prime. We hold this case for later. We then can would do the case n+1 Therefore we can plug in n+1 where n was previously. 2^(n+1) = v for some integer v Using properties of exponents 2^n * 2^1 = v We then plug back in the case where 2^n=2 Therefore, 2* 2 = v There is also prime factors for this 2^2 N is the prime factorization for the result.

Answer 3

All $n > 1$ are a factor of themselves, therefore all primes have a prime factor which is themselves. If we assumed there was a number X that was the smallest number to have no prime factors, then it would not be able to prime and it would have to have at least one factor p, smaller than itself (otherwise it would be prime). If p itself has a prime factor r, then r would also be a factor of X - since it can be seen that if X = qp, and q = rs, then r divides into X sp times

so p can have no prime factors - but we said that X was the smallest number with no prime factors, and p is smaller than X, so by contradiction, X can not exist.

Answer 4

You start from "all integers in $[2,n-1]$ have a prime factor".

Then $n$

• is either a prime, so that it is a prime factor of itself,

• or it is composite, so that it has a factor smaller than itself, let $m$. $m$ is such that $m\in[2,n-1]$ so that by the induction hypothesis, it has a prime factor, which is also a factor of $n$.

You conclude that "all integers in $[2,n]$ have a prime factor".

---

Illustration:

$12$ is composite, $12=2\cdot6$, $2$ has a prime factor ($2$) and so has $12$.

$13$ is a prime, then it has the prime factor $13$.

$14$ is composite, $14=2\cdot7$, $2$ has a prime factor ($2$) and so has $14$.

$15$ is composite, $15=3\cdot5$, $3$ has a prime factor ($3$) and so has $15$.

...