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.
2026-03-26 03:11:30.1774494690
On
On
On
On
On
On
On
On
On
On
On
Infiniteness of non-twin primes.
12.9k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
13
There are 13 best solutions below
0
On
One possibility: Adapt Euclid's proof to show that there are infinitely many primes $p\equiv 1\pmod{3}$.
9
On
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.
0
On
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.
11
On
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.
2
On
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$.]
2
On
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.
0
On
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.
0
On
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.
2
On
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$.
0
On
"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$.
0
On
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.
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.