Special cases of Dirichlet's theorem 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?
 A: As Daniel has pointed out, there is an elementary proof
that for each $n$ there are infinitely many primes $p$
with $p\equiv1 \pmod n$. There is an also an elementary
proof that for each $n$ there are infinitely many primes
$p$ with $p\equiv-1 \pmod n$. This can be found in Nagell's
Introduction to Number Theory section 50 in the second
edition.
A: I found this generalization of the "$3 \pmod{4}$" version while teaching number theory a few years ago.
Let $G$ be a proper subgroup of $(\mathbb{Z}/n)^\times$.  Then there are infinitely many primes $p$ such that $[p]\in (\mathbb{Z}/n)^\times$ and $[p]\not\in G$.
Proof:  Suppose as usual that there are finitely many, $p_1, p_2, \ldots, p_r$, and find a number $g$ such that $(p_i,g) = 1$ for all $i$ and $[g]\not\in G$.  Then the number $N = np_1 p_2 \cdots p_r + g$ has a prime factorization $N = q_1q_2 \cdots q_s$ satisfying

*

*$q_i \neq p_j$ for all $i$ and $j$ and

*since $[N]=[g]\not\in G$, $[q_i]\not\in G$ for at least on $i$.

EDIT 8-29-20
Here is a detailed proof.  There's a bit of fun messing around to find the right number $N$.
Theorem. Let $m\in \mathbb{N}$ and let  $G\subseteq (\mathbb{Z}/m)^\times$  be a proper subgroup.  Then  %for each  %$\alpha\in (\mathbb{Z}/m)^\times - G$,  there are infinitely many primes $p$ such that  $[p] \in (\mathbb{Z}/m)^\times - G$.
Proof.
Assume to the contrary that there are only finitely
such primes,
$$
\mathcal{P}
=
\{
\mbox{all primes $p$ such that 
$[p] \in (\mathbb{Z}/m)^\times -G$}
\}
=
\{ p_1, p_2, \ldots, p_r\}.  
$$
Since each
$[p_i]\in (\mathbb{Z}/m)^\times$
we have $(p_i,m) = 1$ for $i= 1, 2, \ldots, r$.
Since $G$ is a proper subgroup of $(\mathbb{Z}/m)^\times$,
we can find an integer $a$ such that
$[a]\in (\mathbb{Z}/m)^\times - G$;
again $(a, m) = 1$.
Now we inductively define a sequence of integers
$N_k$ for $k = 0, 1, 2, \ldots, r$ with the properties

*

*$N_k \equiv a$ mod $m$

*$(p_i, N_k) = 1$ for $i=1, 2, \ldots, k$.

The construction begins with
$
N_0 = mp_1p_2 \cdots p_r + a  .
$
Once we have $N_k$, we define
$$
N_{k+1} = 
\left\{ 
\begin{array}{ll}
N_k  & \mbox{if $(p_{k+1}, N_k) = 1$}
\\
\\
N_k + m p_1p_2\cdots p_k & \mbox{if $p_{k+1} | N_k$.}
\end{array}
\right.
$$
Obviously
$N_{k+1} \equiv N_k\equiv a$ mod $m$,
and $N_{k+1} \equiv N_k$ mod $p_i$ for each
$i = 1, 2, \ldots, k$, so that
$$
(N_{k+1}, p_i) = (N_k , p_i) = 1
$$
for $i = 1, 2, \ldots, k$.  Furthermore,
if $p_{k+1}| N_k$, then $p_{k+1}$ cannot
divide $N_{k+1}$, lest $p_{k+1}$ divide
$m p_1p_2\cdots p_k$, which is impossible.  Therefore
the construction continues, and ultimately
obtain the integer $N_r$.
Now consider  its prime factorization
$
 N_r = q_1q_2 \cdots q_s
 $.
We can say from what we have done that

*

*$q_j \neq p_i$ for any $i$ and $j$, so
$[q_j]  \in G$ for all $j =1, 2, \ldots, s$, and so

*$[N_r] = [q_1]\cdot [q_2] \cdots [q_s] \in G$,  but

*$[N_r] = [ a] \not\in G$.

This contradiction of the last two lines
shows that our assumption that
there are only finitely many such primes $p$
such that $[p]\in (\mathbb{Z}/m)^\times - G$
must be wrong,
and this completes the proof.
A: There is a simple non-analytic proof for $p\equiv 1 \bmod n$; see e.g. Proposition $3$ in this note.  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 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 by Keith Conrad expositing this impossibility theorem and giving some background.
Edit 2:  Here is the paper 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.
