If $p_1$ and $p_2$ are primes, prove that there exists an integer such that $p_1+k$ is a prime but $p_2+k$ is not.

Let $P_{1}$ and $P_{2}$ be primes. Prove that there exists a $k\in \Bbb Z^+$ such that $P_{1} + k$ is a prime but $P_{2} + k$ is not.

It seems like the proof should be trivial, but for some reason, I am not able to construct it.

Any help would be appreciated.

Solution 1:

Note that the numbers $P_1+nP_2, n\in \mathbb N$ are in arithmetic progression and this contains (by Dirichlet) infinitely many primes. So choose $n\ge 1$ which makes this a prime. $P_2+nP_2$ is clearly not prime.

Solution 2:

Here is a more elementary approach than just quoting Dirichlet.

Suppose $P_2\gt P_1$ and $P_2-P_1=d$. If $P_3=P_1+k$ we want $P_3+d=P_2+k$ not to be a prime.

So given $d$ we need to find a prime $P_3$ with $P_3+d$ not a prime.

Now we know that there are arbitrarily large gaps between primes e.g. $n!+2, \dots n!+n$ gives a gap of size at least $n-1$. (all these are composite by construction, so the prime before and the prime after will have a big gap)

We can choose $n\gt d+1$ here, so there will be a $P_3$ distance greater than $d$ from the next prime, and we can choose $k$ to pick this out.

Solution 3:

Assume wlog $p_1 < p_2$ and $p_1+k$ is prime iff $p_2+k$ is prime. Set $z:=p_2-p_1$. By induction, $p_1+nz$ is prime for all $n$. This is impossible since the primes have density zero.

Solution 4:

Hint: We must assume $P_1 \ne P_2$ for this to be true. Now, what would the world look like if this were false? Well, take $d = |P_1 - P_2|$. If this were false, then either for all $x$ $x \ge P_1$ being prime implies $x + d$ is also prime, or for all $x$ $x \ge P_2$ being NOT prime implies $x + d$ is also NOT prime. In either case, deduce the following absurd fact:

• The function $f: \mathbb{N} \to \mathbb{N}$, defined by $f(n) = 1$ if $n$ is prime and $f(n) = 0$ otherwise, is eventually periodic with period $d$.

From here there are probably multiple ways to derive a contradiction. One idea: there are infinitely many primes, so there must be some $N$ such that $N, N + d$, $N + 2d$, $N + 3d$, etc. are all prime. Now pick $k$ so that $N + kd$ just certainly cannot be prime.