Let be an integer. Define a sequence of positive integers by and
for all . Prove that for each integer there exists a prime number dividing but none of the numbers .
Solution
Let and . It is easy to see that , , and
It is clear that is an increasing sequence. To prove the original statement, it suffices to prove the corresponding statement for the sequence .
We first prove three lemmas:
(1) Lemma 1: If , then .
This lemma is equivalent to . Fix ; this is clearly true for . If , then we have
Hence by mathematical induction, the proof is complete.
(2) Lemma 2: If and , then .
This lemma is equivalent to . Fix , and note that this holds for . Proceeding by induction in a manner similar to the previous item yields the result.
(3) Lemma 3: For all , we have .
Note that the lemma is clearly true for . For , by monotonicity we know , so
hence by mathematical induction, the proof is complete.
Returning to the original problem. By Lemma 3, there exists a prime and a positive integer such that divides but does not divide . We will now show that this is the required by the problem.
If not, let be the smallest positive integer satisfying . By Eq. (1), and are coprime, and , so we have . Write , where and . By Lemma 1, we know that and are congruent modulo , so ; but by the minimality of , this means , and hence .
Now, by Lemma 2, we have that and are congruent modulo . Let be the maximum value such that . By the argument above, we know , while . But this forces , contradicting the maximality of . Contradiction! This completes the proof.