A special case of Dirichlet's Theorem

Our goal here is to prove that there are infinitely many primes $p$ with $p \equiv 1 \pmod m$. We will follow (in a different order) the approach outlined in the exercises of section 13.6 of Dummit and Foote.

We first state two results.

Result 1. Let $P(x) \in \mathbb Z[x]$ be a monic polynomial of degree at least one. Then there are infinitely many distinct prime divisors of the integers $P(1), P(2), P(3), ...$.

Result 2. Let $a \in \mathbb Z$. Then if $p$ is an odd prime dividing $\Phi_m(a)$ then either $p$ divides $m$ or $p \equiv 1 \pmod m$.

Let's suppose these are true, and consider $\Phi_m(1), \Phi_m(2), ...$. These (together) have infinitely many prime divisors by result 1. All of these prime divisors must be even, divide $m$, or be 1 mod $m$ by result 2. Since only finitely many primes can be even or divide $m$, infinitely many primes are 1 mod $m$.

We proved the desired result assuming result 1 and result 2, so now it just suffices to prove these.

Proof of result 1:

Suppose $p_1, ..., p_k$ are the only primes dividing $P(1), P(2), ...$. Let $N$ be such that $P(N) \neq 0$, and let $a = P(N)$. Now let $Q(x) = a^{-1} P(N + ap_1 ... p_kx)$. Note that all the coefficients of $Q(x)$ are integers by applying the binomial theorem and the fact that $P(N) = a$. Again applying the binomial theorem and the fact that $P(N) = a$, we see that $Q(n) \equiv 1 \pmod {p_1...p_k}$ for all positive integers $n$. Therefore, there is an integer $M$ such that $Q(M)$ has a prime factor different from $p_1, ..., p_k$ (since $Q(x) = \pm 1$ can only have finitely many solutions).

It now follows that $P(N + a p_1...p_kM) = aQ(M)$ has a prime factor different from $p_1, ..., p_k$, completing the proof of result 1.

Proof of result 2:

Let $p$ be an odd prime not dividing $m$. Suppose $\Phi_m(a) \equiv 0 \pmod p$. We claim that the order of $a$ mod $p$ is $m$.

Suppose the order is $d$, which must divide $m$. Then $\Phi_d(a) \equiv 0 \pmod p$ (since $a$ is a primitive $d$-th root of unity!). Now we have, if $d \neq m$,
$$x^m - 1 = \prod_{c \mid m} \Phi_c(x) = \Phi_m(x) \Phi_d(x)h(x)$$
for some polynomial $h(x)$. This means that $x^m - 1$ has $a$ as a multiple root, a contradiction. (This is a contradiction since $x^m - 1$ is separable, since its derivative $mx^{m - 1}$ is relatively prime to it, since $p \nmid m$.)

Now that we know that the order of $a$ mod $p$ is $m$, we also know $m \mid p - 1$, so $p \equiv 1 \pmod m$, completing the proof of result 2.