In this recent question the asker was looking for a proof of the existence of infinitely many prime numbers $p$ such that both $p-2$ and $p+2$ are composite. A highly upvoted answer by Ege Erdil made the point that all the primes of the form $p=15n+8$ qualify. They then called upon Dirichlet's theorem of primes in an arithmetic progression to reach an affirmative answer.

I would like to see an "elementary" proof of the infinitude of primes in an arithmetic progression that fits in here. So I generalize Ege's recipe to the following question:

Is there an example of a pair of integers $(a,n)$ such that $\gcd(a-2,n)>1$, $\gcd(a+2,n)>1$, and that there is an elementary proof for the infinitude of primes $p\equiv a\pmod n$?

Your definition of "elementary" may vary. I'm leaving that somewhat open on purpose, but at least anything more elementary than $L$-functions will qualify.

This may prove to be taxing. There is no shortage of elementary proofs for the infinitude of primes in an arithmetic progression on our site:

However, those methods don't really work for the purposes of my question. That's because there is a deeper result due to Murty and Thain, locally referred to here, stating that a "Euclid style" proof for the infinitude of prime $p\equiv a\pmod n$ exists if and only if $a^2\equiv1\pmod n$.

This rules out Euclid style proofs as an option. For if $a^2\equiv1\pmod n$, then $n\mid a^2-1$. But, together with this, the conditions $\gcd(a-2,n)>1$ and $\gcd(a+2,n)>1$ imply that $$1<\gcd((a-2)(a+2),n)=\gcd(a^2-4,n)=\gcd(3,n).$$ That gcd can thus only be $3$, but it is obvious that $3$ cannot be a factor of both $a-2$ and $a+2$.

So something else is needed! This may be a tall order, but I'm asking this in case this rings a bell.

A "Euclid style" proof means roughly the following: Assume that we have an exhaustive (finite) list of primes $p_1,\ldots,p_k$ in a given residue class. Then a cleverly chosen polynomial $P$ evaluated at $p_1p_2\cdots p_k$ can be shown to have a prime factor in this residue class, but not equal to any of $p_i$. Ergo, there must be infinitely many such primes. In other words, mimicking Euclid's classical proof for the infinitude of primes.

  • 1
    $\begingroup$ Anyone recalling other threads where particular residue classes are handled is welcome to add them to the list! $\endgroup$ May 5, 2019 at 13:31
  • 3
    $\begingroup$ This proof by Erdos should apply, since $15=2\cdot 3$ and $\frac{1}{2}+\frac{1}{7}+\frac{1}{11}+\frac{1}{13}<1$. $\endgroup$
    – logarithm
    May 5, 2019 at 14:53
  • 1
    $\begingroup$ The Erdos method was also sketched in a related MO thread, where some related wok is cited. $\endgroup$ May 5, 2019 at 16:55
  • 1
    $\begingroup$ @log how is $15=2×3$? Typo maybe? $\endgroup$ Sep 16, 2019 at 14:32
  • 1
    $\begingroup$ Let $\pi$ be the set of primes and let $P$ be the set of primes that belong to a prime pair. You want to show there are infinitely many $n\in \Bbb N$ such that if one of $6n\pm 1$ is prime then the other one is composite. If this were false then every sufficiently large prime would belong to $P$, implying $\sum_{p\in P}1/p=\infty $(...because $\sum_{p\in \pi}1/p=\infty$...). But it has been shown that $\sum_{p\in P}1/p<\infty.$ I don't know whether this result is deep. I have not seen the proof. $\endgroup$ Nov 14, 2020 at 2:17

1 Answer 1


We may use following statement:

There are infinitely many odd numbers such as q which are the difference and also the sum of two primes . Clearly one these primes must be 2:


$at+b=p_2-2$$at +b+2=p_2$

The necessary condition for primality of $p_1$ and $p_2$ is that $a$, $t$ and $(b-2)$ for $p_1$ also $a$, $t$ and $ (b+2)$ for $p_2$ have no common divisors(Legendre - Dirichlet theorem), and sufficient condition is that $at+b-2$ and $at+b+2$ must be primes. For example for numbers $a=37$ and $b=11$ we have:



Now for $t=10$ we get $p_1=379$ and $p_2=383$ and $q=383-2=379+2=381$

Now we can construct a number like p such that:

$$p=kn+a ; k∈N; (n, a+2)=c_1>1; (n, a-2)=c_2>1$$

To respond the required condition n must be a multiple of factors $a+2$ and $a-2$, also p must be odd, so $kn$ must be even. Hence the form of required number can be as follows:

$$p= k.2(q+2)(q-2)+q; k∈N$$

So that:

$gcd[n=2(q^2-4),(a=q )-2=q-2]>1$


$gcd[n=2(q^2-4),(a=q )+2=q+2]>1$

For example $q=381$:

$p= k (2\times 379 \times 383) +381$

Among these infinite odd numbers there may be infinitely many primes. May be brute force help us to find such primes.

Next is to show that there are infinitely many prime p of the above form. For a certain value of q, relation $p= k.2(q+2)(q-2)+q$ can either be written for k In form of $ak+1$, because $p= k.2(q+2)(q-2)+q$ is odd, so is q and we can write:

$$p= k.2(q+2)(q-2)+q=2[(q^2-4).k+(q-1)/2].x+1$$

Which can be prime generator of the form $(ax+1)$ and due to Legendre- Dirichlet theorem can give infinitely many primes, or it can be written for t if we put $p_1=at+b-2=q-2$ and $p_2=at+b+2=q+2$ in relation $p= k.2(q+2)(q-2)+q$ and find a quadratic polynomial for t. For example for $q=381$ we get:


This polynomial can generate primes if it is not reducible in Q and also the coefficients $2738$, $1628k+37$ and $234k+11$ are relatively primes which is possible for certain values of k.

Here are few primes constructed using $q=381$ and generator $p=2kq^2+q-8k$ or $(2q^2-8)k+q$:

($k=3$$p=871323$),($k=4$$p=1161637$), ($k=10$$p=2903521$).

  • $\begingroup$ $p\equiv 383\pmod{762}$ is NOT a solution: A) $\gcd(385,762)=1$, but the requirement is that both $a-2$ and $a+2$ should have a common factor with $n$. B) you haven't given a proof that there are infinitely many primes $p$ such that $p\equiv383\pmod{762}$. $\endgroup$ May 6, 2019 at 9:49
  • $\begingroup$ Jyrki Lahtonen, Oh I see, it seems I have to delete my answer, at least I gave an idea!Thanks for your respond anyway! $\endgroup$
    – sirous
    May 6, 2019 at 10:41
  • $\begingroup$ @JyrkiLahtonen, I edited my answer. I will try to prove the infinite number of this form of primes in my next edit. $\endgroup$
    – sirous
    May 6, 2019 at 16:37
  • 1
    $\begingroup$ I think most elementary proofs that there are infinitely many primes $\equiv a \bmod q$ are based on those ideas $\endgroup$
    – reuns
    May 7, 2019 at 17:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .