Dirichlet's theorem on arithmetic progressions

Remarks

The hypothesis $\gcd(a, d) = 1$ is necessary. Each term of $a + n d$ is a multiple of $\gcd(a, d)$, so at most one term can be prime when $\gcd(a, d) > 1$. For $d = 4$, the theorem gives infinitely many primes $p \equiv 1 \pmod 4$ and infinitely many primes $p \equiv 3 \pmod 4$. A special case with an elementary proof is that there are infinitely many primes congruent to 1 modulo n. The primes are in fact equally distributed among the $\varphi(d)$ possible classes, where $\varphi$ is Euler's totient function.

History

Dirichlet proved the theorem in 1837. His proof introduced Dirichlet characters and Dirichlet $L$-functions.