Prove that every integer 
is either prime or is a product of primes.
Proof. The proof is by induction. If
or 
, then 
is prime, so the statement is true.Now assume that the statement is true for all integers from 2 up to
. We want to show that this implies 
is either prime or a product of primes. If is prime then there is nothing to show and we are done. On the other hand, if is not prime, then we know there are integers 
and 
such that 
(i.e., is divisible by numbers other than 1 and itself).By the induction hypothesis, since
we know that and are either prime or are products of primes. But then 
and so is a product of primes (since the product 
is a product of primes, whether and are primes or products of primes themselves).Hence, if the statement is true for all integers greater than 1 up to
then it is also true for ; hence, it is true for all 
In the inductive step the assumption is that k is either prime or a product of primes c and d. Then for k + 1, k + 1 is prime (in which case the proof is over) or a product of two integers c’ and d’ such that k + 1 = c’d’. But in your proof you seem to just take it that c = c’ and d = d’. Perhaps I am missing something but this does not seem like a valid proof.
Apostol doesn’t address this kind of “strong” induction in the text, but I’m unaware of how to prove this with the “weak” version that he does provide. So this exercise feels a bit sneaky. It’s possible to prove a form of strong induction following a similar line of reasoning as the proof to Theorem I.36 (Princinple of Mathematical Induction).
In this context, the two seem to be equivalent:
http://www.math.ucsd.edu/~benchow/SS216/Induction.pdf
Prove that every integer greater than 1 has a prime devisor
Please tell me why k+1=cd
its just a assumption. its given in question itself, and as a matter of fact its called “remainder theorem”. He just assumed k+1 to be product of 2 random integers c and d