# Dirichlet's theorem on arithmetic progressions

The theorem can be found on Wikipedia.

In the subsection "Proof" Wikipedia says that there is a proof for the case $a=1$ which uses no calculus, instead splitting behavior of primes in cyclotomic extensions. Could you help me proving this?

Assumption. For every natural number $n$ there are infinitely many prime numbers $p\equiv 1 \pmod n$.

Proof: I assume there are only finitely many $p_1,...,p_i$, and let $P=p_1\cdot...\cdot p_i$. The cyclotomic polynomial

$$\phi_n(x):=\prod_{\gcd(k,n)=1,\ 1\le k<n}(x-\zeta_n^k)\;,\;\;\zeta_n=\cos\frac{2\pi}{n}+i\sin\frac{2\pi}{n}$$

The hint in Neukirch books states that not all numbers $\phi_n(xnP)$ for $x\in\mathbb Z$ can equal $1$. Why? Now let $p \mid \phi_n(xnP)$ for suitable $x$. How can a contradiction be followed from this?

• You mean, for a fixed $x \in \mathbb{Z}$ and varying $n \in \mathbb{N}$, not all $\phi_n(x n P)$ can equal to 1? Otherwise, if $n$ is fixed and $x$ varies, if for all $x \in \mathbb{Z}$, $\phi_n(x n P) = 1$, then $\phi_n - 1$ has infinitely many zeros, hence it's a zero polynomial, a contradiction. – xyzzyz Apr 26 '13 at 10:53
• Thanks, yes thats what I meant. Do you also have an idea for a contradiction for the last part, i.e why there have to be infinitely many prime numbers? – Babla Apr 26 '13 at 10:55
• The contradiction is not so different from Euclid's proof for primes: any prime $p$ which divides $\Phi_n(y)$ must be relatively prime to $y$, and either divide $n$ or be congruent to $1$ mod $n$. – Erick Wong Apr 26 '13 at 13:18
• Thanks, but where is the contradiction? – Babla Apr 26 '13 at 16:49

That there are infinitely many primes $p \equiv 1 \pmod{n}$ for any fixed $n \in \mathbb{Z}^+$ is a nice application of some elementary properties of cyclotomic polynomials. A proof can be found in $\S$ 10.1 of my field theory notes, which begins by defining cyclotomic polynomials and establishing these properties.