Proof that for all distinct primes $p, q$, there exists $n$ so that $p+n$ is prime, but $q+n$ isn't

Imagine two distinct prime numbers $p$ and $q$. Intuitively, I'd say that there is always a natural number n so that $p+n$ is a prime number, but $q+n$ isn't.

I was given two hints:

• for each natural number $n$ there is a prime $p$ so that $n < p \leq 2n$
• consider the primorials

But I still can't come up with a mathematical proof. My main problem is that I don't understand how I can show that the sum of a prime and another number is a prime. Any help?

-
What is your motivation and background? – Brandon Carter Nov 13 '11 at 22:50
Did you really intend to write $n < p \le p$ ? – Joel Cohen Nov 13 '11 at 23:01
@JoelCohen: Oops, I meant to write n < p <= 2n. – cactus1987 Nov 13 '11 at 23:07
@BrandonCarter: I need this to prove the non-regularity of a formal language using the Myhill-Nerode theorem. – cactus1987 Nov 13 '11 at 23:10

We first show that if $p$ and $q$ are primes such that $p<q$, there is a positive integer $n$ such that $p+n$ is prime but $q+n$ is not. Then we complete the proof by showing that if $p>q$, there is an $n$ such that $p+n$ is prime but $q+n$ is not.

Case $p<q\;$: Let $d=q-p$. Let $k$ be the smallest positive integer such that $p+kd$ is not prime. (There are non-primes of the form $p+id$, take for example $i=p$.)

Note that $k>1$. Then $q+(k-1)d$ is not prime, but $p+(k-1)d$ is prime. Now let $n=(k-1)d$.

Case $p>q\;$: Let $r$ be the smallest prime greater than $p!$, and let $n=r-p$. Then $q +n=r-p+q$ is composite, since there are at least $p-1$ consecutive non-primes ending at $r-1$.

Comment: The "large gaps" idea that was used for the case $p>q$ could also be used to deal with the case $p<q$. We used instead an even simpler idea.

In the arguments above, no use is made of Bertrand's Postulate. Primorials were not used, but could have been. In the proof for the case $p>q$, one can use the product of the primes $\le p$ where $p!$ was used.

-
And if $q\lt p$? – Gerry Myerson Nov 13 '11 at 23:17
@Gerry Myerson: Thanks! In editing, somehow the $p<q$ condition disappeared. – André Nicolas Nov 13 '11 at 23:43

By Dirichlet theorem, there exists a $k$ so that $p+kq$ is prime... Can you finish the proof?

-
Yes, because q + kq = q * (k + 1), which is obviously not a prime number. I'm not sure whether I'm "allowed" to use the Dirichlet theorem, though. – cactus1987 Nov 13 '11 at 23:15

The question is equivalent to asking for existence of a prime number $A$ (larger than $p$) such that $A + (q-p)$ is not prime. In fact, almost all primes satisfy this condition; the number of primes $A$ up to $x$ is about $x/\log(x)$ while the number with both $A$ and $A+k$ prime is $O(x/(\log x)^2)$, for any fixed integer $k$. The latter estimate is an upper bound and can be proved by Brun's sieve. Proving a nontrivial lower bound is a variant of the twin prime conjecture.

You can see here the tradeoff between the strength of the method of proof, and the density of the set of primes constructed.

The quantitative twin prime and prime k-tuples conjecture implies that the fraction of primes less than $x$ satisfying the conditions is $1 - C_k / \log(x) + o(1/\log x)$, for an explicit rational number $C_k$ calculable from $k$.

Sieve theory shows that the fraction is $1 - o(1)$, and actually at least $1 - \frac{c}{\log x}$, for a larger constant than the one from the prime k-tuplet conjectures. This is the correct magnitude for the error term, but with the wrong constant.

Factorial or "primorial" constructions of arithmetic progressions of intervals of composite numbers (in which $A$ is chosen to be the nearest prime to the interval) capture almost all primes. This fact implies, and is implied by, the statements whose proofs use sieve theory, so is no easier to prove. The error term is of the same type, $O(1/\log x)$ with non-optimal constant.

Dirichlet's theorem shows that the fraction is positive and at least $1/\phi(p) + o(1)$.

-
In terms of the original problem statement, $A$ and $A+ (q-p)$ are equal to $p+n$ and $q+n$, respectively. – zyx Nov 14 '11 at 3:44