# Euclid-style proof of Dirichlet’s theorem on primes in certain arithmetic progression

The well-known theorem of Dirichlet on primes in arithmetic progression states that given coprime natural numbers $$a\le q$$, there are infinitely many prime numbers congruent to $$a\pmod q$$. The standard proof is via analytic number theory; however, the special case $$a=1, q=2$$, is a celebrated theorem of Euclid, whose proof was essentially extended by Euler using cyclotomic polynomials to all cases $$a=1$$. This elementary algebraic approach — let’s call it Euclid-style proof — of using polynomials to resolve special cases of Dirichlet’s theorem is known to be impossible only if $$a^2\not\equiv 1\pmod q$$, which is (sometimes) known in the field as Schur-Murty Impossibility Theorem (after Issai Schur and Ram Murty). My question is

Has anyone been able to give a generic Euclid-style argument for every case $$a^2\equiv1\pmod q$$ (or any partial results to that effect)?

(Precisely, by “Euclid-style”, we mean the existence of a polynomial $$p$$ whose prime factors over (a sequence of) natural number arguments contains a prime congruent to $$a\pmod q$$; the simplest, non-trivial and well-known examples are $$p(x)=4x-1$$ for $$a=3\,,q=4$$, and $$p(x)=4x^2+1$$ for $$a=1\,,q=4$$.)

A proof of the construction of a polynomial, in English, is in the paper of Murty and Thain, Primes in Certain Arithmetic Progressions (Funct. Approx. Comment. Math. 35 (2006) pp. 249-259, doi:10.7169/facm/1229442627). See Section 2, which builds up to the Euclid-style proof as Theorem 6. In the proof is a typographical error: the defining displayed formula for $$f(x)$$ should have $$f(x)$$, not $$f(x)^2$$, on the left side of the formula.

The proof is illustrated afterwards for $$p \equiv 4 \bmod 15$$, but there is another typographical error: $$f(x)$$ here is the minimal polynomial of $$\zeta + \zeta^{4}$$ over $$\mathbf Q$$, which is $$x^4 - x^3 + 2x^2 + x + 1$$; it is written there with the linear term $$x$$ missing.

The basic idea of the proof can be described briefly if you know Galois theory. Let $$\zeta_m$$ be a root of unity of order $$m$$, such as $$e^{2\pi i/m}$$. When $$a \bmod m$$ has order $$2$$, $$\{1,a\}$$ is a subgroup of $$(\mathbf Z/(m))^\times$$, and $${\rm Gal}(\mathbf Q(\zeta_m)/\mathbf Q) \cong (\mathbf Z/(m))^\times$$ in a standard way by Galois theory. Therefore the subfield of $$\mathbf Q(\zeta_m)$$ fixed by $$\{1,a\bmod m\}$$ using Galois theory is a field $$L$$ of degree $$\varphi(m)/2$$ over $$\mathbf Q$$. Write $$L = \mathbf Q(\eta)$$ for some number $$\eta$$ and take as $$f(x)$$ the minimal polynomial of $$\eta$$ over $$\mathbf Q$$. We'd like $$f(x)$$ to be in $$\mathbf Z[x]$$, so let $$\eta$$ be an algebraic integer generating $$L$$. By a careful choice of $$f(x)$$, every prime factor of $$f(n)$$ for for $$n \in \mathbf Z$$ is either a factor of $${\rm disc}(f)$$ or is congruent to $$1$$ or $$a \bmod m$$. They use $$f(x)$$ to give a Euclid-style proof that there are infinitely many primes $$p \equiv a \bmod m$$ assuming there is at least one such prime. If there are only finitely many primes congruent to $$a \bmod m$$ then they use that finiteness to get a contradiction using the Chinese remainder theorem, so there are infinitely many such primes.

As an example, if $$a = 4$$ and $$m = 15$$ then $$\zeta_{15} + \zeta_{15}^4$$ generates the subfield of $$\mathbf Q(\zeta_{15})$$ fixed by $$\{1,4\bmod 15\}$$, and the minimal polynomial of $$\zeta_{15} + \zeta_{15}^4$$ over $$\mathbf Q$$ is the polynomial I mentioned earlier: $$x^4 - x^3 + 2x^2 + x + 1$$. With this polynomial you can give a Euclid-style proof that there are infinitely many primes $$p \equiv 4 \bmod 15$$.

It is natural to think that you should always be able to use $$\eta = \zeta_m + \zeta_m^a$$, since that sum definitely is fixed by $$\{1, a\bmod m\}$$. But watch out: we need to make sure $$\zeta_m + \zeta_m^a$$ is not fixed by anything else in $${\rm Gal}(\mathbf Q(\zeta_m)/\mathbf Q)$$ in order to know it generates the subfield fixed by $$\{1,a \bmod m\}$$ rather than a smaller field.

Example 1. When $$a = -1$$ this always works: $$\mathbf Q(\zeta_m + \zeta_m^{-1})$$ has degree $$\varphi(m)/2$$ over $$\mathbf Q$$.

Example 2. When $$m = 8$$ and $$a$$ is $$3$$, $$5$$, and $$7$$, this idea works with $$3$$ and $$7$$ but there's a problem with $$5$$. The quadratic subfields of $$\mathbf Q(\zeta_8)$$ are $$\mathbf Q(\sqrt{2})$$, $$\mathbf Q(\sqrt{-2})$$, and $$\mathbf Q(i)$$, and $$\zeta_8 + \zeta_8^3$$ has minimal polynomial $$x^2 + 2$$, $$\zeta_8 + \zeta_8^7$$ has minimal polynomial $$x^2 - 2$$, but $$\zeta_8 + \zeta_8^5$$ is $$0$$, so it doesn't generate the subfield $$\mathbf Q(i)$$ fixed by $$\{1, 5 \bmod 8\}$$.

Example 3. For $$4 \mid m$$ and $$a = 1 + m/2$$, $$a^2 = 1 + m + m(m/4) \equiv 1 \bmod m$$ and $$\zeta_m + \zeta_m^{1+m/2} = \zeta_m - \zeta_m$$ is $$0$$, so $$\zeta_m + \zeta_m^{1+m/2}$$ doesn't generate the subfield of $$\mathbf Q(\zeta_m)$$ fixed by $$\{1, 1+m/2 \bmod m\}$$. Example 2 is the case $$m = 8$$ (so $$a = 1 + m/2 = 5$$).

That is why in the proof of Theorem 6 in Section 2 of Murty and Thain's paper, their chosen generator for the field $$L$$ fixed by $$\{1, a \bmod m\}$$ is not $$\zeta_m + \zeta_m^a$$ (it doesn't always work!), but $$h_u(\zeta_m) := (u - \zeta_m)(u - \zeta_m^a)$$ for an integer $$u$$ and they show $$h_u(\zeta_m)$$ has degree $$\varphi(m)/2$$ for all but finitely many integers $$u$$. Therefore you can take $$\eta = h_u(\zeta_m)$$ for all but finitely many integers $$u$$.

• Theorem 6 of the paper of Murty and Thain states that if $\ell^{2} \equiv 1 \pmod{k}$ and there is at least one prime $p \equiv \ell \pmod{k}$, then there are infinitely many. Does their argument give a way of producing a single prime $\equiv \ell \pmod{k}$ which can be used to apply Theorem 6? Note that the statement "for all $(\ell,k)$ with $\ell^{2} \equiv 1 \pmod{k}$ there is a single prime $p \equiv \ell \pmod{k}$" and "for all $(\ell,k)$ with $\ell^{2} \equiv 1 \pmod{k}$ there are infinitely many primes $p \equiv \ell \pmod{k}$" are equivalent. Commented Jan 17, 2021 at 14:13
• @JeremyRouse you're right, I misread the argument. They do indeed use an assumption of finitely many primes $p \equiv \ell \bmod k$ is an essential way. I've edited my answer above to account for that. I tried now to adapt their proof of Theorem 6 to show that from a finite list of known primes that are all $\equiv \ell \bmod k$ (rather than it being the full list of all such primes) another such prime has to exist, and I'm not able to get things to work out in the way I had hoped. Commented Jan 18, 2021 at 1:40

Yes. According to Paul Pollack's paper Hypothesis H and an impossibility theorem of Ram Murty, Murty gave an argument that an elementary Euclid-style proof is impossible when $$a^{2} \not\equiv 1 \pmod{q}$$, while Schur proved that if $$a^{2} \equiv 1 \pmod{q}$$, then there is an elementary Euclid-style argument that there are infinitely many primes $$p \equiv a \pmod{q}$$. Schur's paper Über die Existenz unendlich vieler Primzahlen in einigen speziellen arithmetischen Progressionen (in German) can be found online, and I believe the elementary argument that there are infinitely many primes $$p \equiv a \pmod{q}$$ is given in Section 4.

I do not read German well. From other sources, I gather that the technique is the following. Assume that $$a \not\equiv 1 \pmod{q}$$. One can construct a polynomial $$p(x)$$ so that if $$n$$ is a positive integer, every prime divisor of $$p(n)$$ either divides $$q$$ or is $$\equiv 1 \text{ or } a \pmod{q}$$. One can construct such a polynomial by taking the minimal polynomial of $$\zeta_{q} + \zeta_{q}^{a}$$ over $$\mathbb{Q}$$, where $$\zeta_{q} = e^{2 \pi i / q}$$. However, there is some subtlety in turning this into an elementary proof that there are infinitely many primes $$\equiv a \pmod{q}$$, since one needs to begin by finding an integer $$n$$ so that $$p(n)$$ has a prime factor $$\equiv a \pmod{q}$$ that divides $$p(n)$$ to an odd power.

EDIT: As clearly explained by KConrad, $$\zeta_{q} + \zeta_{q}^{a}$$ need not be a primitive element for the fixed field of $$\{ 1, a \} \subseteq (\mathbb{Z}/q\mathbb{Z})^{\times} \cong {\rm Gal}(\mathbb{Q}(\zeta_{q})/\mathbb{Q})$$.

• Negation missing in 1st congruence? Commented Jan 16, 2021 at 22:59
• Thanks for the correction. Commented Jan 17, 2021 at 2:07
• It's not always true that $\zeta_q + \zeta_q^a$ works, since it may have smaller degree than $\varphi(q)/2$, e.g., $\zeta_8 + \zeta_8^5$ is $0$. You have to work with a symmetric expression in $\zeta_q$ and $\zeta_q^a$ a bit more involved than their sum to be sure you have something with degree $\varphi(q)/2$ over $\mathbf Q$. See my answer for what can be done. Also, you don't need to find a prime $\equiv a \bmod q$ first, since you show by contradiction that no finite list of such primes is all of them, and thus in particular the set of such primes is not empty. Commented Jan 17, 2021 at 3:45
• It would be nice to classify all $q$ and $a$ such that $a^2 \equiv 1 \bmod q$, $a \not\equiv 1 \bmod q$, and $\zeta_q + \zeta_q^a$ has degree less than $\varphi(q)/2$. There's no example with $a = -1$. My answer mentions a family of examples: $4 \mid q$ and $a = 1 + q/2$. Are there further examples? Commented Jan 18, 2021 at 0:23
• I found a paper by Conway and Jones ("Trigonometric Diophantine Equations (On Vanishing Sums of Roots of Unity)", Acta Arith. 30 (1976), 229-240) at matwbn.icm.edu.pl/ksiazki/aa/aa30/aa3033.pdf that discusses how a sum of roots of unity or cosines can be $0$, focusing on "minimal relations" where no subsum is $0$. Viewing $\zeta_q + \zeta_q^a - \zeta_q^j - \zeta_q^{aj} = 0$ as a relation, if it were not minimal then a subsum of two terms is 0. The three possibilities lead to $j \equiv 1 \bmod q$, $j \equiv a \bmod q$, and lastly $\zeta_q = -\zeta_q^a$ (contd.) Commented Jan 18, 2021 at 6:51