CYCLOTOMIC POLYNOMIALS

1. Introduction

Let ζ = e^{2πi/n}. Then ζ, ζ^{2}, …, ζ^{n} are the n n^{th} roots of unity. They form the vertices of a regular n-gon in the complex plane. If (a, n) > 1 then ζ^{a} is a root of unity of order n/(a, n) < n, but if (a, n) = 1 then ζ is not a root of lower order, and in this case we call ζ^{a} a primitive n^{th} root of unity. We define the n^{th} cyclotomic polynomial Φ_{n}(x) to be the monic polynomial of degree ϕ(n) whose roots are the primitive n^{th} roots of unity:

(1)  Φ_{n}(x) = ∏_{\begin{matrix}a=1 \\ (a,n)=1 \end{matrix}}^{n}(x − ζ^{a}).

Our first observation concerning cyclotomic polynomials is that

(2)  z^{n} − 1 = ∏_{d|n} Φ_{d}(x).

To see this, it suffices to classify roots of unity ζ^{a} according to the value of (a, n). Thus we see that

z^{n} − 1 = ∏_{a=1}^{n}(x − ζ^{a})

= ∏_{d|n} ∏_{\begin{matrix}a=1 \\ (a,n)=n/d \end{matrix}}^{n}(x − ζ^{a}).

Write a = bn/d where (b, d) = 1 and 1 ≤ b ≤ d. Then the above is

= ∏_{d|n} ∏_{\begin{matrix}b=1 \\ (b,d)=1 \end{matrix}}^{d}(x − ζ^{bn/d})

= ∏_{d|n} Φ_{d}(x).

Our next task is to show that Φ_{n}(x) has integral coefficients. To establish this, we induct on n. We note that Φ_{1}(x) = x − 1 has integral coefficients. Suppose that Φ_{d}(x) has integral coefficients for all d < n. Put

G_{n}(x) = ∏_{\begin{matrix}d|n \\ d<n \end{matrix}} Φ_{d}(x).

Then by the inductive hypothesis, G_{d}(x) has integral coefficients. Suppose that F (x) and G(x) are polynomials with integral coefficients. Then by the division algorithm there is a quotient polynomial Q(x) and a remainder polynomial R(x) such that F (x) = G(x)Q(x) + R(x) and deg R < deg G. In general, the coefficients of Q(x) and R(x) are rational numbers, but if G(x) is monic then the coefficients of Q(x) and R(x) are integers. We apply this with F (x) = x^{n} − 1, G(x) = G_{n}(x). Then R(x) is identically 0 and Q(x) = Φ_{n}(x).

The identity (2) can be inverted by the Möbius inversion formula to yield a formula for Φ_{n}(x) in terms of the polynomials x^{d} − 1:

(3)  Φ_{n}(x) = ∏_{d|n}(x^{d} − 1)^{μ(n/d)}.

Since

\frac{1}{1 − x^{d}} = 1 + x^{d} + x^{2d} + x^{3d} + ⋯,

it is evident that the right hand side of (3) is a power series with integral coefficients. This provides a second means of seeing that Φ_{n}(x) has integral coefficients.

The first few cyclotomic polynomials are as follows:

Φ_{1}(x) = x − 1,
Φ_{2}(x) = x + 1,
Φ_{3}(x) = x^{2} + x + 1,
Φ_{4}(x) = x^{2} + 1,
Φ_{5}(x) = x^{4} + x^{3} + x^{2} + x + 1,
Φ_{6}(x) = x^{2} − x + 1,
Φ_{7}(x) = x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1,
Φ_{8}(x) = x^{4} + 1,
Φ_{9}(x) = x^{6} + x^{3} + 1,
Φ_{10}(x) = x^{4} − x^{3} + x^{2} − x + 1,
Φ_{11}(x) = x^{10} + x^{9} + x^{8} + x^{7} + x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1,
Φ_{12}(x) = x^{4} − x^{2} + 1,
Φ_{13}(x) = x^{12} + x^{11} + x^{10} + x^{9} + x^{8} + x^{7} + x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1,
Φ_{14}(x) = x^{6} − x^{5} + x^{4} − x^{3} + x^{2} − x + 1,
Φ_{15}(x) = x^{8} − x^{7} + x^{5} − x^{4} + x^{3} − x + 1,
Φ_{16}(x) = x^{8} + 1.

It is noteworthy that the coefficients of the above polynomials take only the values ±1 and 0. At one time this was conjectured to apply to all cyclotomic polynomials, but Φ_{105}(x) provides a counter-example, and we now know that there are cyclotomic polynomials with very large coefficients. This occurs particularly when n is highly composite.

2. Primitive roots modulo p

Euler used cyclotomic polynomials to prove the existence of primitive roots mod p. Gauss dismissed Euler’s argument as incomplete, because Euler did not properly develop the material in the preceding section. To reconstruct how Euler might have reasoned, we take n = p − 1 in (2) to see that

x^{p−1} − 1 = ∏_{d|(p−1)} Φ_{d}(x).

Since the left hand side has p − 1 roots modulo p, each Φ_{d}(x) on the right hand side must have ϕ(d) roots (mod p), and moreover if d and e are distinct divisors of p − 1, then the roots of Φ_{d}(x) (mod p) must be disjoint from the roots (mod p) of Φ_{e}(x).

Lemma 1. If a has order h modulo p, then Φ_{h}(a) ≡ 0 (mod p).

Proof. From (2) with n = h and x = a, we see that the left hand side is a multiple of p, and hence p|Φ_{d}(a) for some d|h. From (2) again we see that Φ_{d}(x) divides (x^{d} − 1) in ℤ[x], and hence Φ_{d}(a)|(a^{d} − 1). Hence a^{d} ≡ 1 (mod p). By the minimality of h, it follows that d = h, so the proof is complete.

Lemma 2. If Φ_{d}(a) ≡ 0 (mod p) and d|(p − 1), then a has order d.

Proof. Let h denote the order of a modulo p. Since Φ_{d}(a)|(a^{d}−1), we have a^{d} ≡ 1 (mod p), and hence h|d. From Lemma 1 we also know that p|Φ_{h}(a). That is, Φ_{d}(x) and Φ_{h}(x) have a common root a (mod p). This implies that d = h.

On combining these lemmas we see that if h|(p − 1), then the roots (mod p) of Φ_{h}(x) are precisely the residue classes of order h. Thus there are exactly ϕ(h) residue classes of order h. In particular, there are exactly p − 1 residue classes of order p − 1, which is to say primitive roots.

Lemma 2 is false if the hypothesis d|(p − 1) is omitted. To see this, note that Φ_{p}(1) ≡ 0 (mod p), but 1 does not have order p modulo p; it has order 1. Nevertheless, Lemma 2 can be extended, as follows.

Lemma 3. If Φ_{n}(a) ≡ 0 (mod p), then a has order n (mod p), or p|n.

Proof. Let h denote the order of a modulo p. Since a^{n} ≡ 1 (mod p), it follows that h|n. If h = n, then we are done. Suppose that h < n. Then Φ_{h}(x) and Φ_{n}(x) are distinct factors of x^{n} − 1. Moreover, Φ_{h}(x) has a factor x − a modulo p, and so does Φ_{n}(x). Hence F_{n}(x) = x^{n} − 1 has a factor (x − a)^{2} modulo p. Hence F′_{n}(x) has a factor x − a modulo p. But

(4)  nF_{n}(x) − xF′_{n}(x) = −n

is a polynomial identity. Substitute x = a. Since p|F_{n}(a) and p|F′_{n}(a), it follows that p|n.

One consequence of Lemma 3 is that if n ∤ (p − 1) and p ∤ n, then the congruence Φ_{n}(x) ≡ 0 (mod p) has no solution.

3. Primes ≡ 1 (mod m)

We prove that there are infinitely many prime numbers p ≡ 1 (mod m). This is a special case of a theorem of Dirichlet, which asserts that if (a, m) = 1 then there exist infinitely many prime numbers p ≡ a (mod m). Since the assertion is trivial for m = 1, we may suppose that m ≥ 2. Suppose that p_{1}, p_{2}, …, p_{r} are primes that are ≡ 1 (mod m). We show that there is at least one more such prime. Set x = mp_{1}p_{2} ⋯ p_{r}, and let p be a prime factor of Φ_{m}(x). Note that x ≥ 2, so that each factor on the right hand side of (1) has absolute value > 1. Hence |Φ_{m}(x)| > 1, which ensures that Φ_{m}(x) does indeed have at least one prime factor. By Lemma 3 it follows that p|m or that x has order m modulo p. But x ≡ 0 (mod m), which implies that Φ_{m}(x) ≡ Φ_{m}(0) ≡ 1 (mod m). Hence p ∤ m, and consequently x has order m modulo p. But then m must divide p − 1, which is to say that p ≡ 1 (mod m).

To see how this works numerically, we note that

Φ_{8}(101) = 2 · 89 · 584609,  Φ_{10}(101) = 11 · 9367291,
Φ_{8}(102) = 5857 · 18481,  Φ_{10}(102) = 61 · 251 · 7001,
Φ_{8}(103) = 2 · 56275441,  Φ_{10}(103) = 1171 · 95191,
Φ_{8}(104) = 17 · 1657 · 4153,  Φ_{10}(104) = 5 · 211 · 109831.

On the left we encounter 2 and primes ≡ 1 (mod 8), and on the right we have 5 and primes ≡ 1 (mod 10).

4. Irreducibility of cyclotomic polynomials

In this section we show that the cyclotomic polynomial Φ_{n}(x) is irreducible over the field ℚ of rational numbers.

Let p denote a given prime number. For any polynomial F (x) with integral coefficients let \overline{F} (x) be the polynomial whose coefficients are the residue classes (mod p) determined by the coefficients of F (x). Thus the assertion \overline{F} = \overline{G} means that there is a polynomial H(x) with integral coefficients such that F (x) = G(x) + pH(x).

Lemma 4. (Schönemann, 1846) Let A(x) be a monic polynomial with integral coefficients, say

A(x) = x^{n} + a_{n−1}x^{n−1} + ⋯ + a_{0} = ∏_{i=1}^{n}(x − α_{i}).

Let p be a prime number, and put

C(x) = ∏_{i=1}^{n}(x − α_{i}^{p}).

Then \overline{C} = \overline{A}.

Proof. Let σ_{k}(α) denote the k^{th} symmetric function of the α_{i}. When σ_{k}(α)^{p} is expanded by the multinomial theorem, all coefficients except the extreme ones are divisible by p. That is,

\frac{σ_{k}(α_{1}, α_{2}, …, α_{n})^{p} − σ_{k}(α_{1}^{p}, α_{2}^{p}, …, α_{n}^{p})}{p}

is a symmetric polynomial in the α_{i} with integral coefficients, and hence by the symmetric function theorem this quantity is a rational integer.

Lemma 5. Put F (x) = x^{n} − 1. Then \overline{F} is squarefree if and only if p ∤ n.

Proof. By the identity (4) we see that if p ∤ n, then (\overline{F} , \overline{F′}) = 1, and hence that \overline{F} is squarefree. On the other hand, if p|n, say n = mp, then \overline{F} = \overline{x^{m} − 1}^{p}, and hence \overline{F} is not squarefree.

Let Φ_{n}(x) denote the n^{th} cyclotomic polynomial. Since Φ_{n}|F, it follows from the above that if p ∤ n, then \overline{Φ_{n}} is squarefree.

Theorem. (Kronecker, 1854) The polynomial Φ_{n}(x) is irreducible over the field ℚ of rational numbers.

Proof. Suppose that A and B are monic polynomials with rational coefficients such that Φ_{n} = AB, and suppose also that deg A > 0. By Gauss’s lemma we know that A and B have integral coefficients. Let 𝒵 denote the roots of A. Let C be the monic polynomial whose roots are the numbers ζ^{p} for ζ ∈ 𝒵. Here p is an arbitrary prime not dividing n. Our first step is to show that A = C. Since the map ζ ↦ ζ^{p} merely permutes the roots of Φ_{n}, we know that C | Φ_{n}. Let G = (B, C). Then \overline{G} | \overline{B} and \overline{G} | \overline{C}. But \overline{A} = \overline{C} by Lemma 4, and hence \overline{G}^{2} | \overline{A} \overline{B} = \overline{Φ_{n}}. But \overline{Φ_{n}} is squarefree, by Lemma 5. Hence \overline{G} = \overline{1}, so G = 1, and consequently C | A. But C and A have the same degree, so in fact A = C.

Now let ζ be a root of A, and ζ′ a root of Φ_{n}. Then there exists a positive integer a, (a, n) = 1, such that ζ′ = ζ^{a}. We factor a, a = p_{1}p_{2} ⋯ p_{k}. Since ζ is a root of A, it follows from the argument above that ζ^{p_{1}} is also a root of A. Then by a second application of the above argument, we see that ζ^{p_{1}p_{2}} is also a root of A. Continuing in this manner, we deduce that ζ′ is a root of A. Since this is valid for every root ζ′ of Φ_{n}, we conclude that A = Φ_{n}. Hence Φ_{n} is irreducible.

Gauss proved that Φ_{p} is irreducible. The first proof of Kronecker’s theorem using Schönemann’s theorem was given by Arndt in 1857. An alternative argument using Schönemann’s theorem is found in the text of Nagell. Among the more elementary proofs, the one of Landau (1929) is remarkable for its brevity: only 8 lines. A detailed account of the various proofs has been given by K. Manteuffel, Wiss. Zeit. Tech. Hochschule Magdeburg 1 (1957), 69–75.