0
$\begingroup$

There is following example given in a book. I am not sure how do we conclude that $a$ is divisible by prime? See this section:

Case 2 ($k + 1$ is not prime): In this case $k+1=ab$ where $a$ and $b$ are integers with $1 < a < k+1$ and $1 < b < k+1.$ Thus, in particular, $2≤a≤k$, and so by inductive hypothesis, a is divisible by a prime number $p$.

Here is the entire example:

Strong Induction example:

Show that for all integers $k ≥ 2$, if $P(i)$ is true for all integers $i$ from $2$ through $k$, then $P(k + 1)$ is also true:

Let $k$ be any integer with $k ≥ 2$ and suppose that $i$ is divisible by a prime number for all integers $i$ from $2$ through $k$.

We must show that

Case 1 ($k + 1$ is prime): In this case $k + 1$ is divisible by a prime number, namely itself.

Case 2 ($k + 1$ is not prime): In this case $k+1=ab$ where $a$ and $b$ are integers with $1<a<k+1$ and $1<b<k+1$. Thus, in particular, $2≤a≤k$, and so by inductive hypothesis, $a$ is divisible by a prime number $p$. In addition because $k + 1 = ab$, we have that $k + 1$ is divisible by $a$. Hence, since $k + 1$ is divisible by $a$ and $a$ is divisible by $p$, by transitivity of divisibility, $k + 1$ is divisible by the prime number $p$.

Therefore, regardless of whether $k + 1$ is prime or not, it is divisible by a prime number.

$\endgroup$
1
  • $\begingroup$ Taken from pp. 269-270 of the fourth edition of Susana S. Epp's book: Discrete Mathematics with Applications. Just for anyone who's curious... $\endgroup$
    – JakeD
    Commented Nov 1, 2016 at 23:24

1 Answer 1

1
$\begingroup$

A prime number can only has divisors of $1$ and itself. So if $k+1$ is not prime, then it can be written as the product of two integers less than it, which implies that $k+1 = ab$ such that $a, b \neq k + 1$. So by the Inductive Hypothesis, a prime divides $a$ and a prime divides $b$. It follows that since $b|(k+1)$ and a prime $p|b$ that $p|(k+1)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .