some friends and I are stuck on a proof regarding primes. It goes as follows:

Let $p_1, p_2$ be primes with $p_1 < p_2$. Show that there is a $n \in > \mathbb{N}$ such that $p_1 + n \cdot (p_2 - p_1)$ is prime, but $p_2 +$ $n \cdot (p_2 - p_1)$ is not. $Hint:$ Chose a small $n$.

We tried several things but didn't come close to a solution.

I'd appreciate any help, approaches or solutions.



First let's try $n=1$. Of course $p_2=p_1+1\times (p_2-p_1)$ is prime. If $2p_2-p_1$ is composite we are done, so assume it is prime.

Accordingly, try $n=2$. Under the assumption that $2p_2-p_1$ is prime, we now ask if $3p_2-2p_1$ is composite. If it is composite, we are done, so assume it is prime.

Continue in this manner. At each point we ask whether $np_2-(n-1)p_1$ is composite. The first composite of this form would be an example of what you want (though a priori they might all be prime).

To see that they can not all be prime, note that the sequence of test cases $\{2p_2-p_1,3p_2-2p_1,\cdots\}$ is just the sequence $2p_2-p_1+k(p_2-p_1)$ It is easy to see that no arithmetic progression can contain only primes (take $k=2p_2-p_1$ for example). Thus this sequence contains infinitely many composites, so we are done. (the first composite in the list gives you your example).

Worth remarking that this argument only shows existence. Well, it shows that there has to be an example with $n≤2p_2-p_1$ but other than that it does not actually produce an example.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.