Dirichlet's theorem states that for any coprime $k$ and $m$ there exists infinitely many primes $p$ such that $p \equiv k \pmod m$.


Some special cases of this theorem are easy to prove without any analytic methods. Those cases include, for example, $m=4, k=1$ and $m=4, k=3$.


Both cases could be proved by considering first $t$ prime numbers $p\_i \equiv k \pmod m$ and constructing a new number which is proved to have prime divisor $p \equiv k \pmod m$ that is not equal to any $p\_i$.


For case $m=4, k=1$ we can consider number $(p\_1 p\_2 \cdots p\_t)^2 + 1$. And for case $m=4, k=3$ number $4p\_1 p\_2 \cdots p\_t + 3$.


Those constructions could also be applied to some other special cases as well.


Are there any other special cases for which there exists a simple non-analytic proof which don't use any of those two constructions?



Special cases of Dirichlet's theorem
There is a simple non-analytic proof for $p\equiv 1 \bmod n$; see e.g. Proposition $3$ in [this note](https://static1.squarespace.com/static/57bf2a6de3df281593b7f57d/t/57bf68b26a49636398ee2dce/1472161971095/primes1mod4.pdf). The proof gives a (Euclidean) argument that infinitely many primes divide the values of an integer-coefficient polynomial on the integers, and then notes that the prime divisors of the values of the $n$-th cyclotomic polynomial either divide $n$ or have remainder $1$ upon division by $n$. (The proof is well-known; I don't know the originator.) By the way, the note also contains a cute analytic argument for $p\equiv 1 \bmod 4$ giving bounds on the partial sums of the reciprocals of such primes; the argument uses representations via sums of two squares.


Edit: [This paper](https://projecteuclid.org/journals/functiones-et-approximatio-commentarii-mathematici/volume-35/issue-none/Primes-in-Certain-Arithmetic-Progressions/10.7169/facm/1229442627.full) by Murty and Thain discusses obstructions to Euclid-style proofs for various congruence classes. I believe that a proof has been carried out for $p\equiv a\bmod b$ for $(a, b)=1$ for $b= 24$ in the style of Euclid, however.


Here is an open-access [paper](http://www.math.uconn.edu/%7Ekconrad/blurbs/gradnumthy/dirichleteuclid.pdf) by Keith Conrad expositing this impossibility theorem and giving some background.


Edit 2: Here is the [paper](https://www.jstor.org/stable/2310975) I recalled with the Euclidean proof for $b= 24$; unfortunately it is not open-access. It is JSTOR however so many of you likely have institutional access.


