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

Question

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

Answer 1

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

Answer 2

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