# Proof that there are infinitely many prime numbers $p$ such that $p-2$ is not prime.

Just need verification of this proof by contradiction:

Let $p_k$ be the largest prime number such that $p_k-2$ is not a prime number. Let $p_l$ be some prime number such that $p_l > 3p_k$. We know that $p_l$ exists because there are infinitely many prime numbers as proven elsewhere.

$p_l-2$ is a prime number. $p_l-4$ is a prime number as well. By induction, all numbers $p_k < x < p_l | x \mod 2 = 1$ are prime numbers. But $p_k<3p_k<p_l$ and $3p_k \mod 2 = 1$ and $3|3p_k$ so there is a contradiction.

Also would love to see more concise proofs if at all possible.

Edit:

Great that I got so many people trying to provide their own proof but the question was primarily asked so that I could have my proof verified. Only skyking addressed my question, though I do not yet understand his criticism.

• How about a proof by counterexample: $23-2=21$ not a prime? Commented Nov 11, 2015 at 13:40
• @Aniket One is not very far on the way to proving infinitely many. Commented Nov 11, 2015 at 13:40
• Since one of $p_t, p_t-2, p_t-4$ must be a multiple of $3$, it should suffice to take $p_t>p_k+4$. Anyway, I think your proof method (using only the infinitude of prime and not Dirichlet) is best Commented Nov 11, 2015 at 13:41
• @ThomasAndrews: And an careful observation would reveal that it is not even a counterexample!!! Commented Nov 11, 2015 at 13:51

It is very simple to construct such infinite sequence:

$$35+60n,37+60n$$

$35+60n$ will generate an infinite amount of composite numbers, all of which are divisible by $5$ (in fact, it will generate only composite numbers).

$37+60n$ will generate an infinite amount of prime numbers, since $37$ and $60$ are coprime integers (according to Dirichlet's theorem on arithmetic progressions).

• That could be boiled down a lot: There are infinitely many primes $\equiv -1\pmod 6$ and for these $p-2$ is a multiple of $3$. Commented Nov 11, 2015 at 13:42
• Off course, using the fact that there are infinitely many primes $\equiv-1\pmod6$, it is much more obvious. But this fact is not so obvious by itself. Commented Nov 11, 2015 at 13:43
• +1 for an easy answer avoiding the temptation to use Dirichlet's theorem on arithmetic progressions Commented Nov 11, 2015 at 13:47
• @PVanchinathan: I take it you're being slightly cynical? Commented Nov 11, 2015 at 13:48
• @quid: Yes, I agree, please read my comment right below that "+1" comment. Commented Nov 11, 2015 at 14:40

You can use the simple fact that the numbers $n$, $n+2$, $n+4$ are all incongruent mod $3$, so that at least one of them must be a multiple of $3$. Thus the only triple of numbers $(n,n+2,n+4)$ consisting of all primes is $(3,5,7)$.

If $p_k$ denotes the $k^{th}$ prime and $k$ is the largest index for which $p_k - 2$ is not prime, then $p_{k+2} - 2 = p_{k+1}$ and $p_{k+1} - 2 = p_k$. Thus $(p_k,p_k+2,p_k+4)$ is a triple of primes, implying $p_k = 3$, which is an obvious contradiction.

Note that if a prime $p>5$ is of the form $3n+2$ then $p-2$ is not prime.

There are infinitely many primes of the form $3n+2$. This follows at once from Dirichlet's Theorem, but it can be shown directly (Pf: were the list finite we could list all the examples, $\{p_1, \dots, p_k\}$ but then $P=3*\prod {p_i}-1$ is prime to everything on our list and is clearly not the product of primes of the form $3n+1$.)

First of all some criticism, the proof seem to be somewhat overly complicated. But I see no fault in it.

It's not that clear that $p_l-4$ is a prime number, not using the fact that $p_k$ being the largest prime such that $p_k-2$ is not a prime at least.

The statement however follows quite easily from two observations:

1. There are infinite number of primes
2. There are infinite number of odd composite numbers (non-primes)

For each odd composite number $k$ there exists a smallest prime $p(k)>k$. Now since it's the smallest such prime you have that $p(k)-2$ is not a prime ($p(k)-2\ge k$, either it's $k$ and composite or between $k$ and $p(k)$ and therefore composite).

The first observation is a direct consequence of that $3(2n+1)$ is composite. The second is because otherwise (if there were finitely many primes) the product of all primes plus 1 would be another prime.

• Thanks for actually addressing my proof at all. However I don't understand your criticism. If a prime $p$ is larger than $p_k$ it should obey the property that $p−2$ is a prime, no? So it seems to me that this implies that all odd number between $p_k$ and $p_l$ are primes Commented Nov 11, 2015 at 14:10
• @DaBamti I missed the different indices, but you're correct. The real criticism should be that it's somewhat overly complicated. Commented Nov 11, 2015 at 14:39

Consider multiples of $3$, and add $2$ in them. By Dirichlet's theorem, there are infinitely many primes in $\{ 3n+2\}_n$, and collecting them, subtract $2$ from them, we get non-primes.

• Dirichlet seems like overkill for such a trivial theorem. it certainly works, but... Commented Nov 11, 2015 at 13:44

We can have the obvious case where the last digit of p is 7. By drichlet's theorem on arthmetic progressions, we can generate a sequence of 5*n* + 7, where there are infinitely many primes with last digit as 7

Note: I considered the obvious case since (10k+7)-2 is divisible by 5, thus not prime