Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Well, we all know the twin prime conjecture. There are infinitely many primes $p$, such that $p+2$ is also prime. Well, I actually got asked in a discrete mathematics course, to prove that there are infinitely many primes $p$ such that $p + 2$ is NOT prime.

share|cite|improve this question
What did you try yourself to solve this? – Ragnar Dec 20 '13 at 18:19
My personal favorite – farmerjoe Dec 20 '13 at 22:38
Your title suggests a harder question: to prove that there are infinitely many primes $p$ such that neither $p+2$ nor $p-2$ is prime. This follows immediately from Brun's theorem, but I'm not seeing an easy proof of it otherwise... – Micah Dec 20 '13 at 23:07
@Micah: How about Dirichlet's theorem applied to $15n+7$? $3|p+2$ and $5|p-2$ – Ross Millikan Dec 20 '13 at 23:23
asmeurer: Well, that would be trivial. – Rok Kralj Dec 21 '13 at 20:33

15 Answers 15

Let $p\gt 3$ be prime. If $p+2$ is not prime, we are happy. If $p+2$ is prime, then $(p+2)+2$ is not, since one of $x,x+2,x+4$ is divisible by $3$.

Added: Dolda2000 noted that a more interesting question is whether there are infinitely many primes that are not members of a twin pair. For this we can use the fact that there are infinitely many primes of the form $15k\pm 7$. If $p$ is such a prime, then one of $p-2$ or $p+2$ is divisible by $3$, and the other is divisible by $5$, so if $p\gt 7$ then neither $p-2$ nor $p+2$ is prime.

share|cite|improve this answer
I think this answer seems a bit exploitative of the strict definition given by the question. Even if $(p + 2) + 2$ is not prime, $p + 2$ is still, by any reasonable definition, a twin prime as long as $p$ is prime. It's just that it's the upper twin of the pair rather than the lower. Isn't a more reasonable theorem to prove that there are infinitely many primes $p$ such that neither $p + 2$ nor $p - 2$ are prime? – Dolda2000 Dec 21 '13 at 17:31
@AndréNicolas: Sweet! How do you know that one of x, x+2, x+4 is divisible by 3? I enumerated all the possible sum-of-digits to verify this for myself, but it's not intuitive at all... oh and simpler with the remainders - either you have remainder 0 and you happy, remainder 1 and you add 2 and you're happy, or remainder 2 and you add 4 and you're happy... hmm this is neat, something i have to remember – Claudiu Dec 21 '13 at 22:53
@Claudiu: One could produce a similar argument with digit sums, but as you point out remainders work much more smoothly. The notion of congruence introduced by Gauss works even more nicely. We can prove in a similar way that for any odd $k$, one of $x,x+2,x+4,\dots, x+2(k-1)$ is divisible by $k$. – André Nicolas Dec 21 '13 at 23:02
@MichaelHardy: The question in the body of the post does not ask for a proof that there are infinitely many primes which are not members of a twin pair. To prove the latter stronger assertion, we can use the fact that there are infinitely many primes $p$ of the form $15k+7$. Then if $k\gt 0$, neither $p-2$ nor $p+2$ is prime. – André Nicolas Dec 22 '13 at 1:36
@MichaelHardy: It is a good question, though perhaps a little difficult for a first discrete math course. – André Nicolas Dec 22 '13 at 1:46

Suppose the contrary. This would mean that from some point on, all odd numbers are prime numbers.

Take two sufficiently large odd numbers. Multiply them together. The result is a composite number which is odd, which contradicts the hypothesis that all sufficiently large odd numbers are primes.

share|cite|improve this answer
I like it. Quite different than all the other responses and so simple. – Ross Millikan Dec 20 '13 at 23:25
I'm confused. The contrary is the statement, "There are finitely many primes $p$ such that $p+2$ is also prime." This statement would be easily satisfied if $\{2, 3, 5\}$ were the only primes in the world, which is clearly not the same thing as saying "all odd numbers are prime numbers"... did I misread what you wrote? – Mehrdad Dec 21 '13 at 2:37
The negation is "There are finitely many primes $p$ such that $p+2$ is not also prime." This is equivalent to "For any sufficiently large prime $p$, $p+2$ is also prime." Since there are infinitely many primes, at least one of them is sufficiently large, so the proof goes through. – Micah Dec 21 '13 at 3:31
@Mehrdad The idea is you are supposing there are finitely many primes $p$ such that $p+2$ is not prime. Lets say that $p_n$ is the last prime such that $p+2$ is not prime. Let $p_{n+1}$ be the next prime, so $p_{n+1}+2$, $p_{n+1}+4$,... are all prime. So at some point on all odd numbers are prime numbers. We have that $p_{n+1}(p_{n+1}+2)$ is an odd number that is not prime contradicting that at some point on all odd numbers are prime. – Paul Plummer Dec 21 '13 at 3:35
Like some presentations of Euclid's proof of infinitely many primes, there is no need for contradiction, and it simplifies the argument to eliminate the indirect part of the logic. You argue, essentially, to take $p$ to be the largest prime below any odd composite number. That is a complete (and direct) solution in seven words! – zyx Dec 21 '13 at 6:03

Dirichlet's Theorem guarantees the existence of infinitely many primes of the form $p = 3n+1$, and for each of these, $p+2$ is a multiple of 3.

share|cite|improve this answer

For any integer $x$, either $x$ or $x+2$ or $x+4$ is divisible by $3$, so if $p$ is a prime $> 3$, either $p$ or $p+2$ is an example.

share|cite|improve this answer

Euler proved that the sum of the reciprocals of the primes diverges. Brun proved that the sum of the reciprocals of the twin primes converges. The sum of the reciprocals of the non-twin primes must diverge, so there are infinitely many.

share|cite|improve this answer
Brun first proved the more basic fact that nearly all primes are not twins, which is a stronger form of this problem. – zyx Dec 21 '13 at 23:23

One possibility: Adapt Euclid's proof to show that there are infinitely many primes $p\equiv 1\pmod{3}$.

share|cite|improve this answer

I'm very surprised to see that no one has brought the Prime Number Theorem to bear on this problem yet, so allow me to use that to prove a generalization of the OP's statement:


For every integer $n$, there are infinitely many prime numbers $p$ such that $p+n$ is not prime.


Assume the contrary. That means that for every sufficiently large prime $p$, $p+n$ (and thus $p+2n, p+3n, ...$) is also prime. Therefore, the asymptotic density of the prime numbers in the integers is at least $\frac{1}{n}$, which contradicts the Prime Number Theorem because the PNT implies that the asymptotic density of the primes in the integers is $0$.

share|cite|improve this answer
i upvoted this but the prime number theorem is not necessary for proving that primes have density can prove this without the P.N.T. – Konstantinos Gaitanas Dec 24 '13 at 11:33
To add to Konstantinos Gaitanass' comment, here you can find some proofs that $d(P)=0$:… – Martin Sleziak May 10 '15 at 12:11

Most primes are islands in the composite sea. For every $N$, the fraction of primes at distance more than $N$ from their nearest prime neighbors (both above and below) converges to $1$. This follows from accepted conjectures on the distribution of primes, where the density of a prime/composite pattern goes down by a factor of $c \log x$ for every additional prime, and unconditionally (with a more complicated proof) using Brun's sieve.

The number of primes up to $x$ that are at distance $N$ or more from their nearest prime neighbors, is therefore about $\frac{x}{\log x}$.

Constructions based on Dirichlet's theorem on primes in arithmetic progression give a lower bound of $\frac{Cx}{\log x}$ where $C \in (0,1)$ is a rational number that depends on the set of small integers $k$ for which $p+k$ is required to not be prime. This is not fundamentally different than listing all primes and removing the ones that don't work, except that it also gives a pre-determined prime $\pi_k$ (independent of $p$) dividing $p+k$, for each $k$ in the set, and that more precise divisibility requirement on the prime pattern reduces the density of solutions by the constant factor $C$.

Given the difficulty of deterministic constructions of primes I don't think there are known solutions that are essentially different from those two.

[Edit: the proof by contradiction using multiplication of odd numbers (panoramix' answer) at first appears to be different, but reduced to its essentials it says to take the largest prime below any odd composite number. This is of the "list all primes and delete counterexamples" type, except that the list consists of all composite $p+2$ instead of all prime $p$.]

share|cite|improve this answer
The existing answers show that the original question can be answered, that there are an infinite set of primes $p$ such that $p+2$ is not prime. – Ross Millikan Dec 21 '13 at 5:21
And this answer shows, among other things, why all those replies are, in the present state of knowledge, necessarily equivalent to either "list all primes and strike out the ones that don't work" (Andre Nicolas' solution) or "impose congruence conditions and take any prime in the arithmetic progression satisfying the congruences" (all the other solutions). @RossMillikan – zyx Dec 21 '13 at 5:24

Another rephrasing of some of the answers here: suppose, for a contradiction, that there are only finite number of such primes. Let $q$ be the largest one. Then, for prime $p > q$, we have that $p+2$, $(p+2)+2$, $((p+2)+2)+2$ and so on are prime. But $p + 2p$ is a contradiction.

share|cite|improve this answer

For each prime number $p_1$ where $p_1>3$ and $p_2=p_1+2$ is also prime ("twin primes", assume there are infinitely many of these)... there exists a number $n$ such that $n=p_2+2$ (also an infinite number of these).

$p_1$ and $p_2$ are primes, so neither of them are divisible by $3$. Since every third odd number greater than $3$ is divisible by $3$, $n$ will always be divisible by $3$ and so, not prime.

On the other hand, if there are a finite number of "twin primes", then there are an infinite number of primes $p$ (all remaining primes) such that $p+2$ is not prime.

share|cite|improve this answer
Are you saying that the twin prime conjecture has been proven? Source? – Daniel R Dec 21 '13 at 22:31
@DanielR - Thanks for catching that (+1). I made an assumption that I did not state. I have included my assumption, and expanded my answer. – Kevin Fegan Dec 22 '13 at 1:27

Let $p$ be an odd prime. Then at least one of $$ p+2, p+4, p+6, p+8$$ must be composite since its final digit must be a $5$. Therefore there is at least one non-twin prime near each odd prime.

share|cite|improve this answer

Given any odd prime $p$, we can find a prime with this property greater than $p$. Take $n$ to be the first odd composite number greater than the prime following $p$, $n-2$ must then be prime and greater than or equal to the prime following $p$, which must be greater than $p$ with $(n-2)+2$ composite.

share|cite|improve this answer

At each stage of Eratosthenes sieve, there is a corresponding cycle of gaps. After sieving by 2,3,and 5, we have G(5#) = 6 4 2 4 2 4 6 2. This is the pattern of 8 gaps (and sum 30) through the sieve. E.g. From 1 to 7 is the first gap 6, then 4 to 11, 2 to 13, 4 to 17, 2 to 19, etc. There is a nice recursion on G(p#), described in 1. A gap between primes is either a gap from the cycle or a sum of consecutive gaps in the cycle.

Just to answer the question as originally posed, if there are not an infinite number of twin primes, then we're done, since there are an infinite number of primes. If there are an infinite number of twin primes, let q and q+2 be twin primes. Then q+2 is such a prime p such that p+2 is not prime; q mod 3 = 2, (q+2) mod 3 = 1, and (q+4)mod 3 =0 (not prime).

To answer the broader question of are there infinitely many primes p such that neither p-2 nor p+2 are prime, look at the variety of constellations (sequences of gaps in the cycle) that develop under recursion. For example, the constellation 6,4 in G(5#). This corresponds to the sequences 30k+1, 30k+7, 30k+11. For every k for which 30k+7 is prime, it is a non-twin prime as requested.

share|cite|improve this answer

Brun's theorem can be used to show that not only are there infinitely many non-twin primes, but they are of relative density 1. That is, just like the n-th prime is about $n\log n,$ the n-th non-twin prime is about $n\log n.$

An alternate approach would be the combinatorial sieve; see section 2.3 in Neil Lyall's notes Sieving and upper bounds for the number of twin primes.

share|cite|improve this answer

"I actually got asked in a discrete mathematics course, to prove that there are infinitely many primes p such that p+2 is NOT prime". (I insert the question here to prevent confusing if it was modified.)
I use only that there are infinitely many prime numbers. (An elementary proof of Euclid.) If $p>3$ ($p$ is prime number) then denote $$ P_{-1}:=\{p|p=3k-1,\text{for some }k\} $$ and $$ P_{1}:=\{p|p=3k+1,\text{for some }k\}. $$ (Every prime number, greater than $3$, has remainder $\pm 1$ dividing by $3$.)

So at least one of them contains infinitely many prime numbers.

(a) If $P_{1}$ contains finitely many prime numbers then the statement is true, because $P_{-1}$ contains infinitely many prime numbers so if $k$ is large enough then $p+2=(3k-1)+2\in P_{1}$ not a prime number.

(b) If $P_{1}$ contains infinitely many prime numbers then the statement is true, because taking them $3|(3k+1)+2$.

share|cite|improve this answer

protected by Asaf Karagila Dec 29 '13 at 20:16

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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