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

As Daniel has pointed out, there is an elementary proof that for each $n$ there are infinitely many primes $p$ with $p\equiv1$ (mod $n$). There is an also an elementary proof that for each $n$ there are infinitely many primes $p$ with $p\equiv-1$ (mod $n$). This can be found in Nagell's Introduction to Number Theory section 50 in the second edition.

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.