6
$\begingroup$

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?

  • 0
    What is your motivation and background?2011-11-13
  • 0
    Did you really intend to write $n < p \le p$ ?2011-11-13
  • 0
    @JoelCohen: Oops, I meant to write n < p <= 2n.2011-11-13
  • 0
    @BrandonCarter: I need this to prove the non-regularity of a formal language using the Myhill-Nerode theorem.2011-11-13

3 Answers 3

6

We first show that if $p$ and $q$ are primes such that $pq$, there is an $n$ such that $p+n$ is prime but $q+n$ is not.

Case $p 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

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.

  • 0
    And if $q\lt p$?2011-11-13
  • 0
    @Gerry Myerson: Thanks! In editing, somehow the $p2011-11-13
5

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

  • 1
    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.2011-11-13
1

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)$.

  • 0
    In terms of the original problem statement, $A$ and $A+ (q-p)$ are equal to $p+n$ and $q+n$, respectively.2011-11-14