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



Euclid-style proof of Dirichlet’s theorem on primes in certain arithmetic progression
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](https://doi.org/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$.


