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.
$\begingroup$
$\endgroup$
7
-
29$\begingroup$ What did you try yourself to solve this? $\endgroup$– RagnarDec 20, 2013 at 18:19
-
6$\begingroup$ My personal favorite $\endgroup$– farmerjoeDec 20, 2013 at 22:38
-
19$\begingroup$ 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... $\endgroup$– MicahDec 20, 2013 at 23:07
-
18$\begingroup$ @Micah: How about Dirichlet's theorem applied to $15n+7$? $3|p+2$ and $5|p-2$ $\endgroup$– Ross MillikanDec 20, 2013 at 23:23
-
4$\begingroup$ asmeurer: Well, that would be trivial. $\endgroup$– Rok KraljDec 21, 2013 at 20:33
|
Show 2 more comments
15 Answers
$\begingroup$
$\endgroup$
9
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.
answered Dec 20, 2013 at 18:24
-
29$\begingroup$ 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? $\endgroup$ Dec 21, 2013 at 17:31
-
1$\begingroup$ @AndréNicolas: Sweet! How do you know that one of
x,x+2,x+4is 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 $\endgroup$– ClaudiuDec 21, 2013 at 22:53 -
2$\begingroup$ @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$. $\endgroup$ Dec 21, 2013 at 23:02
-
6$\begingroup$ @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. $\endgroup$ Dec 22, 2013 at 1:36
-
2$\begingroup$ @MichaelHardy: It is a good question, though perhaps a little difficult for a first discrete math course. $\endgroup$ Dec 22, 2013 at 1:46
$\begingroup$
$\endgroup$
11
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.
answered Dec 20, 2013 at 22:52
-
20$\begingroup$ I like it. Quite different than all the other responses and so simple. $\endgroup$ Dec 20, 2013 at 23:25
-
4$\begingroup$ 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? $\endgroup$ Dec 21, 2013 at 2:37
-
13$\begingroup$ 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. $\endgroup$– MicahDec 21, 2013 at 3:31
-
8$\begingroup$ @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. $\endgroup$– user29123Dec 21, 2013 at 3:35
-
11$\begingroup$ 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! $\endgroup$– zyxDec 21, 2013 at 6:03
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
answered Dec 20, 2013 at 18:26
$\begingroup$
$\endgroup$
1
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.
-
8$\begingroup$ Brun first proved the more basic fact that nearly all primes are not twins, which is a stronger form of this problem. $\endgroup$– zyxDec 21, 2013 at 23:23
$\begingroup$
$\endgroup$
One possibility: Adapt Euclid's proof to show that there are infinitely many primes $p\equiv 1\pmod{3}$.
answered Dec 20, 2013 at 18:22
$\begingroup$
$\endgroup$
2
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:
Theorem:
For every integer $n$, there are infinitely many prime numbers $p$ such that $p+n$ is not prime.
Proof:
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$.
-
$\begingroup$ i upvoted this but the prime number theorem is not necessary for proving that primes have density 0.you can prove this without the P.N.T. $\endgroup$ Dec 24, 2013 at 11:33
-
$\begingroup$ To add to Konstantinos Gaitanass' comment, here you can find some proofs that $d(P)=0$: math.stackexchange.com/questions/82074/… $\endgroup$ May 10, 2015 at 12:11
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
2
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$.]
-
1$\begingroup$ 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. $\endgroup$ Dec 21, 2013 at 5:21
-
2$\begingroup$ 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 $\endgroup$– zyxDec 21, 2013 at 5:24
$\begingroup$
$\endgroup$
2
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.
-
2$\begingroup$ Are you saying that the twin prime conjecture has been proven? Source? $\endgroup$– Daniel RDec 21, 2013 at 22:31
-
$\begingroup$ @DanielR - Thanks for catching that (+1). I made an assumption that I did not state. I have included my assumption, and expanded my answer. $\endgroup$ Dec 22, 2013 at 1:27
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
"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$.
