# Elementary proof for infinitude of primes in an arithmetic progression of a special form

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 Starfall 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 Starfall'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.

• My motivation for asking this is to follow up on my whim from a recent meta discussion. – Jyrki Lahtonen May 5 '19 at 13:03
• Hello, Sorry, I can't understand your question properly, but I think that this is what you are looking for, Theorem 3.7 and Theorem 3.8 In Page 54 of David M Burton's Elementary Number Theory - napocaro.files.wordpress.com/2015/02/… – user427802 May 5 '19 at 13:07
• @AbhasKumarSinha The question is about elementary proofs of a special case of Theorem 3.7 (=Dirichlet's theorem). In other words, calling upon Dirichlet's result is not allowed. – Jyrki Lahtonen May 5 '19 at 13:15
• 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$. – logarithm May 5 '19 at 14:53
• The Erdos method was also sketched in a related MO thread, where some related wok is cited. – Bill Dubuque May 5 '19 at 16:55

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_1+2$$$$at+b-2=p_1$$

$$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:

$$p_1=37t+11-2=37t+9$$

$$p_2=37t+11+2=37t+13$$

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$$

and:

$$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:

$$p=2738t^2+(1628k+37)t+234k+11$$

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$$).

• $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}$. – Jyrki Lahtonen May 6 '19 at 9:49
• Jyrki Lahtonen, Oh I see, it seems I have to delete my answer, at least I gave an idea!Thanks for your respond anyway! – sirous May 6 '19 at 10:41
• @JyrkiLahtonen, I edited my answer. I will try to prove the infinite number of this form of primes in my next edit. – sirous May 6 '19 at 16:37
• I think most elementary proofs that there are infinitely many primes $\equiv a \bmod q$ are based on those ideas – reuns May 7 '19 at 17:43