Proof of the irreducibility of the cyclotomic polynomials by reduction modulo primes

Proof

We first show that $\Phi_n$ has rational coefficients. Then we show that $\Phi_n$ is the minimal polynomial of $\zeta = e^{2\pi i/n}$.

1. Let $n \ge 1$ and $\zeta = e^{2 \pi i / n}$, so $\zeta^k = e^{2 \pi i k / n}$ for every integer $k$. Since $\zeta^n = 1$, the number $\zeta^k$ depends only on $k$ modulo $n$.
2. By the description of the $n$th roots of unity, each of them is $\zeta^k$ for some $0 \le k < n$. There are exactly $n$ of them. So $\zeta^0, \dots, \zeta^{n-1}$ are pairwise distinct.
3. Let $E$ be a field, $F \in E[x]$, and $a_1, \dots, a_m$ pairwise distinct roots of $F$. Then $\prod_{i=1}^m (x - a_i)$ divides $F$. We prove this by induction on $m$; the case $m = 0$ is trivial.
4. For $m \ge 1$, the induction hypothesis gives $F = \prod_{i<m} (x - a_i) \, G$. Then $0 = F(a_m) = \prod_{i<m} (a_m - a_i) \, G(a_m)$, and each $a_m - a_i \ne 0$. So $G(a_m) = 0$, and the factor theorem gives $(x - a_m) \mid G$.
5. By Steps 2 to 4, $\prod_{k=1}^{n} (x - \zeta^k)$ divides $x^n - 1$. Both are monic of degree $n$, so $x^n - 1 = \prod_{k=1}^{n} (x - \zeta^k)$.
6. By the definition, $\Phi_d = \prod (x - e^{2 \pi i j / d})$, over the $j$ with $1 \le j \le d$ and $\gcd(j, d) = 1$.
7. For $1 \le k \le n$, let $e = \gcd(k, n)$, $d = n / e$ and $j = k / e$. Then $d \mid n$, $1 \le j \le d$, $\gcd(j, d) = 1$ and $\zeta^k = e^{2 \pi i j / d}$.
8. Conversely, for $d \mid n$ and such a $j$, put $k = j n / d$. Then $\gcd(k, n) = (n/d) \gcd(j, d) = n/d$, so Step 7 gives back $(d, j)$. So Step 7 is a bijection, and Step 5 becomes $x^n - 1 = \prod_{d \mid n} \Phi_d$.
9. We show by strong induction on $n$ that $\Phi_n \in \Q[x]$. First, $\Phi_1 = x - 1$. For $n > 1$, the product $h = \prod_{d \mid n, d < n} \Phi_d$ is monic and lies in $\Q[x]$ by induction.
10. Division by the monic $h$ in $\Q[x]$ gives $x^n - 1 = q h + r$ with $q, r \in \Q[x]$ and $\deg r < \deg h$. In $\C[x]$ we also have $x^n - 1 = \Phi_n h + 0$ by Step 8. Uniqueness of division in $\C[x]$ gives $\Phi_n = q \in \Q[x]$.
11. Next, a lemma. Let $P \in \Z[x]$ be monic and $P = A B$ with $A, B \in \Q[x]$ monic. Then $A, B \in \Z[x]$.
12. Proof of the lemma. Let $a \ge 1$ be the least integer with $a A \in \Z[x]$. If a prime $\ell$ divides all coefficients of $a A$, then $\ell \mid a$, the leading coefficient. Then $(a/\ell) A \in \Z[x]$, which contradicts the choice of $a$.
13. By Step 12 and the fundamental theorem of arithmetic, $aA$ is primitive. Define $b$ for $B$ in the same way, so $b B$ is primitive.
14. The ring $\Z$ is a Euclidean domain, hence a PID and a UFD. By the product of primitive polynomials, $(aA)(bB) = ab P$ is primitive. But $ab$ divides all its coefficients, so $ab = 1$ and $A, B \in \Z[x]$.
15. Let $f$ be the minimal polynomial of $\zeta$ over $\Q$. It exists because $\zeta$ is a root of $x^n - 1$, so $\zeta$ is algebraic. By irreducibility and divisibility, $f$ is irreducible and $f \mid x^n - 1$.
16. Key claim: if $\omega \in \C$, $f(\omega) = 0$ and $p$ is a prime with $p \nmid n$, then $f(\omega^p) = 0$. Suppose not; we derive a contradiction in Steps 17 to 27.
17. Since $f \mid x^n - 1$, we get $\omega^n = 1$. The minimal polynomial $m_\omega$ of $\omega$ divides $f$. Since $f$ is irreducible and both are monic of positive degree, $f = m_\omega$.
18. Also $(\omega^p)^n = 1$. Let $g$ be the minimal polynomial of $\omega^p$, so $g \mid x^n - 1$. Write $x^n - 1 = f k$ with $k \in \Q[x]$ monic.
19. Then $0 = f(\omega^p) k(\omega^p)$ and $f(\omega^p) \ne 0$, so $k(\omega^p) = 0$. So $g \mid k$, and $x^n - 1 = f g h$ with $h \in \Q[x]$ monic.
20. By the lemma of Step 11, applied to $x^n - 1 = f \cdot (g h)$ and then to $g h = g \cdot h$, the polynomials $f, g, h$ lie in $\Z[x]$.
21. Let $G(x) = g(x^p)$, a monic polynomial in $\Z[x]$. Then $G(\omega) = g(\omega^p) = 0$. By Step 17 and divisibility, $G = f k_2$ with $k_2 \in \Q[x]$ monic. By the lemma, $k_2 \in \Z[x]$.
22. Let $\F_p$ be the field $\Z/p\Z$, and let $u \mapsto \bar{u}$ reduce coefficients modulo $p$. It is a ring homomorphism $\Z[x] \to \F_p[x]$, by the universal property. So $x^n - 1 = \bar{f} \bar{g} \bar{h}$ and $\bar{G} = \bar{f} \bar{k}_2$.
23. The ring $\F_p[x]$ has characteristic $p$. So the Frobenius map $u \mapsto u^p$ is a ring homomorphism. With $\bar{g} = \sum_i b_i x^i$ and Fermat's little theorem $b_i^p = b_i$, we get $\bar{g}^p = \sum_i b_i x^{ip} = \bar{G}$.
24. The polynomial $\bar{f}$ is monic with $\deg \bar{f} = \deg f \ge 1$. Let $q$ be a monic divisor of $\bar{f}$ of least degree among those of degree at least $1$.
25. Then $q$ is irreducible. Suppose $q = a b$ with $\deg a, \deg b \ge 1$. Then $a$, made monic, is a smaller such divisor, by the degree of a product.
26. The ring $\F_p[x]$ is a Euclidean domain, hence a UFD, so $q$ is prime. Since $q \mid \bar{f} \mid \bar{G} = \bar{g}^p$, the definition of a prime element, used $p - 1$ times, gives $q \mid \bar{g}$.
27. So $q^2 \mid \bar{f} \bar{g}$, and $x^n - 1 = q^2 s$ for some $s \in \F_p[x]$. The formal derivative and its product rule give $n x^{n-1} = q (2 q' s + q s')$. Since $p \nmid n$, $n$ is a unit of $\F_p$, so $q \mid x^{n-1}$. Then $q$ divides $x \cdot x^{n-1} - (x^n - 1) = 1$, which is impossible for $\deg q \ge 1$.
28. This proves the key claim. Now let $k \ge 1$ with $\gcd(k, n) = 1$. We show $f(\zeta^k) = 0$ by induction on the number of prime factors of $k$. For $k = 1$ this holds by the choice of $f$.
29. Otherwise $k = p m$ with $p$ prime. Then $p \nmid n$ and $\gcd(m, n) = 1$, since both $p$ and $m$ divide $k$. By induction $f(\zeta^m) = 0$. The key claim with $\omega = \zeta^m$ gives $f(\zeta^k) = 0$.
30. By Steps 2, 6 and 29, the roots $\zeta^k$ of $\Phi_n$ are $\deg \Phi_n$ distinct roots of $f$. A polynomial has at most $\deg f$ roots, so $\deg f \ge \deg \Phi_n$.
31. By Step 10, $\Phi_n \in \Q[x]$, and $\Phi_n(\zeta) = 0$. So $f \mid \Phi_n$, say $\Phi_n = f u$. By Step 30, $\deg u \le 0$, so $u$ is a constant, and $u = 1$ since both are monic.
32. So $\Phi_n = f$, which is irreducible in $\Q[x]$ by Step 15.