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:
- $p\equiv\pm1\pmod4$ (many threads),
- $p\equiv1\pmod n$,
- $p\equiv-1\pmod 6$,
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.