Cyclotomic Polynomials

Cyclotomic polynomials are polynomials whose complex roots are primitive roots of unity. They are important in algebraic number theory (giving explicit minimal polynomials for roots of unity) and Galois theory, where they furnish examples of abelian field extensions, but they also have applications in elementary number theory \((\)the proof that there are infinitely many primes congruent to \( 1\) mod \( n) \) as well as geometry (helping answer the question of which regular polygons are constructible with a ruler and compass).

The \(n^\text{th}\) roots of unity lie on the unit circle as the vertices of a regular \( n\)-gon. If \( \zeta_n = e^{2\pi i/n} =\cos\big(\frac{2\pi}{n}\big)+i\sin\big(\frac{2\pi}{n}\big),\) then the roots consist of \[1,\ \zeta_n,\ \zeta_n^2,\, \ldots,\ \zeta_n^{n-1}.\] These are all \(n\) of the complex roots of the polynomial \( x^n-1.\)

The primitive \(n^\text{th}\) roots of unity are the roots of \( x^n-1 \) that are not roots of \( x^d-1 \) for any smaller \( d \); that is, \( n \) is their multiplicative order. Which roots are these?

Let \( \zeta \) be a primitive \(n^\text{th}\) root of unity. Then the primitive \(n^\text{th}\) roots of unity consist of the powers \( \zeta^k \) with \( 1\le k < n \) and \( \text{gcd}(k,n) = 1 \). There are \( \phi(n) \) of these, where \( \phi \) is Euler's totient function.

If \( 0 < a < n \) and \( (\zeta^k)^a = 1 \), then \( n|ka \). If \( \text{gcd}(n,k) = 1\), then \( n|a,\) which is impossible, so \( \zeta^k \) is a primitive \(n^\text{th}\) root of \( 1 \). If \( \text{gcd}(n,k) = d>1 \), then \( \zeta^{k(n/d)} = \zeta^{n(k/d)} = 1^{k/d} = 1 \), so \( \zeta^k \) is not a primitive \(n^\text{th}\) root of \( 1\). This proves the statement. \(_\square\)

There are twelve \(12^\text{th}\) roots of unity, but only \( \phi(12) = 4 \) of them are primitive, namely \( \zeta_{12}, \zeta_{12}^5, \zeta_{12}^7, \zeta_{12}^{11} \). The other \( 8\) are \( d^\text{th}\) roots of unity for some proper divisor \( d\) of \( 12 \).

Let \( \Phi_n(x) \) be the polynomial with complex coefficients defined by the formula

\[\Phi_n(x) = \prod_{\stackrel{\zeta \text{ a primitive }}{n^\text{th} \text{ root of unity}}} (x-\zeta) = \prod_{\stackrel{1\le k < n }{ \text{gcd}(k,n)=1}} \big(x-\zeta_n^k\big),\]

where \( \zeta_n = e^{2\pi i/n} \).

The order of any \(n^\text{th}\) root of unity is a divisor of \( n\) (by the division algorithm—the argument is the same as the argument for orders mod p), so this definition implies that

\[x^n-1 = \prod_{d|n} \Phi_d(x),\]

which is a formula that will be used later.

• \( \zeta_1 = 1 \), so \( \Phi_1(x) = x-1\).
• \( \zeta_2 = -1 \), so \( \Phi_2(x) = x+1\).
• \( \Phi_3(x) = (x-\zeta_3)\big(x-\zeta_3^2\big) = x^2+x+1 \), because \( \zeta_3 = -\frac12 + i\frac{\sqrt{3}}2 \) and \( \zeta_3^2 = -\frac12 - i \frac{\sqrt{3}}2. \)
• \( \zeta_4 = i \) and the only other primitive \( 4^\text{th}\) root of \( 1 \) is \( -i \), so \( \Phi_4(x) = (x+i)(x-i) = x^2+1 \).
• An easy shortcut for \( \Phi_5(x) \) is this: every \( 5^\text{th}\) root of unity is primitive except for \( 1\), so \( \Phi_5(x) = \frac{x^5-1}{x-1} = x^4+x^3+x^2+x+1 \).
• For \( \Phi_6(x) \), only \( \zeta_6 = \frac12 + i\frac{\sqrt{3}}2 \) and \( \zeta_6^5 = \frac12 - i\frac{\sqrt{3}}2 \) are primitive. So \( \Phi_6(x) = (x-\zeta_6)\big(x-\zeta_6^5\big) = x^2-x+1 \). This could also have been derived via \[ \Phi_6(x) = \frac{x^6-1}{\Phi_1(x)\Phi_2(x)\Phi_3(x)} = \frac{x^6-1}{(x-1)(x+1)(x^2+x+1)} = x^2-x+1.\]

Already some patterns are emerging. The argument for \( \Phi_5(x) \) works for any \( \Phi_p(x) \) where \( p \) is prime, so \( \Phi_p(x) = x^{p-1} + x^{p-2} + \cdots + 1 \). It is immediate from the definition and the result in the above section that the degree of \( \Phi_n(x) \) is \( \phi(n) \).

More fundamentally, notice that the coefficients of \( \Phi_n(x) \) appear to be integers. Slightly more subtle is the fact that \( \Phi_n(x) \) seems to be irreducible over the integers (there are no nonconstant polynomial factors of smaller degree with integer coefficients). Both of these statements will be proved in later sections.

\( \Phi_n(x) \) is a polynomial with integer coefficients, of degree \(\phi(n)\). It is irreducible over the rational numbers \((\)that is, it has no nontrivial factors with rational coefficients with smaller degree than \( \Phi_n), \) so it is the minimal polynomial of \( \zeta_n \).

Show that \( \Phi_n(x) \in {\mathbb Z}[x] \) by induction on \( n \). The base case is clear, and now suppose the result holds for all \( k< n \). Then \[ x^n-1 = \bigg( \prod_{\stackrel{k|n,}{k<n}} \Phi_k(x) \bigg) \Phi_n(x). \] The product in the parentheses is a monic polynomial with integer coefficients, by the inductive hypothesis. Now the result follows from a general divisibility lemma.

Lemma: Suppose \( f(x) = g(x) h(x) \) in \( {\mathbb C}[x]\) and \( f(x) \) and \( g(x) \) are monic polynomials with integer coefficients. Then \( h(x) \) is a monic polynomial with integer coefficients.

Proof of lemma: There is a division algorithm in \({\mathbb Z}[x] \) that works as long as the divisor is monic. Thus we can write \( f(x) = g(x) q(x) + r(x) \) with \( r=0 \) or \( \text{deg}(r) < \text{deg}(g)\), where \( q(x),r(x) \in {\mathbb Z}[x].\) So \[\begin{align} g(x)h(x) &= g(x)q(x)+r(x) \\ g(x)\big(h(x)-q(x)\big) &= r(x), \end{align}\] and if both sides of the equation are nonzero, then the degree of the left side is clearly strictly greater than the degree of the right side, which is impossible; so both sides are zero, \( r(x) = 0 \), and \( h(x) = q(x) \). \(_\square\)

The proof of irreducibility is left for the final, optional section of the wiki.

Note that the coefficient of \( x^{\phi(n)-1} \) in \( \Phi_n(x) \) is the negative of the sum of the primitive \(n^\text{th}\) roots of unity, which is \( -\mu(n),\) where \( \mu\) is the Möbius function (see that wiki for a proof). In general it appears for small examples that the coefficients of \( \Phi_n(x) \) are always \( -1,0,\) or \( 1 \). But in fact this is not the case for all \( n\); the smallest \( n \) for which \( \Phi_n(x) \) has a different coefficient is \(n = 105\). \(\big(\)The coefficient of \( x^{41} \) and \( x^7 \) is \( -2.\big)\)

Applying Möbius inversion to the identity

\[x^n-1 = \prod_{d|n} \Phi_d(x)\]

gives

\[\Phi_n(x) = \prod_{d|n} (x^d-1)^{\mu(n/d)} = \prod_{d|n} (x^{n/d}-1)^{\mu(d)},\]

which is a fairly explicit formula for \( \Phi_n \). It can also be used to prove general facts about relationships between various \( \Phi_n\).

For a positive integer \( n \), let \( r_n = \text{rad}(n) \) be the product of the distinct positive primes dividing \( n \). Then

\[\Phi_n(x) = \Phi_{r_n}(x^{n/r_n}).\]

The divisors \( d \) of \(n\) such that \( \mu(d) \ne 0\) are precisely the divisors of \( r_n\). So

\[\Phi_n(x) = \prod_{d|n} (x^{n/d}-1)^{\mu(d)} = \prod_{d|r_n} \left((x^{n/r_n})^{r_n/d}-1\right)^{\mu(d)} = \Phi_{r_n}(x^{n/r_n}).\]

It is immediate from the theorem that \( \Phi_{96}(x) = \Phi_6(x^{16}) = x^{32}-x^{16}+1.\)

So the \( \Phi_n(x) \) are determined by their values on square-free \( n \). The following theorem can be used to compute these values:

If \( p \nmid m\), \( p \) prime, then \( \Phi_{mp}(x) = \frac{\Phi_m(x^p)}{\Phi_m(x)}. \)

There are two types of divisors of \( mp\), ones divisible by \( p \) and ones that are not. The former can be written as \( pd, d|m \), and the latter can be written as \( d, d|m \). Splitting the product into two products gives

\[\begin{align} \Phi_{mp}(x) &= \prod_{d|m}(x^{mp/pd}-1)^{\mu(pd)} \prod_{d|m}(x^{mp/d}-1)^{\mu(d)}\\ &= \prod_{d|m}(x^{m/d}-1)^{-\mu(d)} \prod_{d|m}\big((x^p)^{m/d}-1\big)^{\mu(d)} \\ &= \Phi_m(x)^{-1} \Phi_m(x^p).\ _\square \end{align}\]

Compute \( \Phi_{180}(x) \).

---

By the first theorem, \(\Phi_{180}(x) = \Phi_{30}(x^6) \).

Now \( \Phi_{30}(x) = \frac{\Phi_6(x^5)}{\Phi_6(x)} \) by the second theorem. This is

\[\frac{x^{10}-x^5+1}{x^2-x+1} = x^8 + x^7 - x^5 - x^4 - x^3 + x + 1,\]

so

\[\Phi_{180}(x) = x^{48} + x^{42} - x^{30} - x^{24} - x^{18} + x^6 + 1.\ _\square\]

Here is one application to the following special case of Dirichlet's theorem on primes in arithmetic progressions. This uses a result about the prime divisors of \( \Phi_n(b) \) for integer \( b\).

Given a positive integer \( n \), there exists a positive integer \( N \) such that a prime divisor of \( \Phi_n(b) \) for some integer \( b \) is either less than \( N \) or congruent to \( 1 \) mod \( n \).

Let \( f(x) = (x-1)(x^2-1)(\cdots)(x^{n-1}-1) \). Then \( f(x) \) and \( x^n-1\) are relatively prime over the complex numbers, hence relatively prime over the rational numbers (by similar arguments as above). So there exist \( a(x),b(x) \in {\mathbb Q}[x] \) such that \( f(x)a(x)+(x^n-1)b(x) = 1 \). Let \( N\) be the product of the denominators of the coefficients of \( a \) and \( b.\) Then clearing denominators gives \( f(x) A(x) + (x^n-1)B(x) = N \), where \( A \) and \( B \) have integer coefficients.

Now suppose \( p>N \) is a prime number dividing \( \Phi_n(b) \). Then \( p|(b^n-1) \), so \( b^n\equiv 1 \pmod p\). Now if \( p|(b^k-1) \) also for some smaller positive \( k \), then \( p|f(b) \) and so \( p|N \), which is impossible. So in fact \( n \) is the multiplicative order of \( b \) mod \( p \). Then Fermat's little theorem implies \( n|(p-1) \), as desired. \(_\square \)

For every \(n\), there are infinitely many primes congruent to \(1 \) mod \( n \).

Suppose there were only finitely many such primes. Let \( c \) equal the product of those primes and the number \( N!, \) where \( N \) is as in the previous theorem. Now \( \Phi_n(x) \to \infty\) as \( x\to\infty\) since it is a monic polynomial, so take \( M \) large enough so that \( \Phi_n(Mc) > 1 \).

Now for \( n \ge 2\), \( \Phi_n(0) = 1 \) (exercise), so \( \Phi_n(Mc) \) is relatively prime to \( c \) (all the other terms but the constant term are divisible by \( c \)). This is a contradiction of the previous theorem, since any prime dividing \( \Phi_n(Mc) \) must divide \( c \) by its construction. \(_\square\)

There are several proofs of irreducibility; the one given here is due to Schur.

First there is a lemma about products involving roots of unity.

Lemma: Let \( \zeta \) be a primitive \( n^\text{th}\) root of unity. Then
\[\prod_{i \ne j} ( \zeta^i-\zeta^j) = \pm n^n,\] where the product runs over pairs of distinct positive integers \( (i,j) \) with \( 0 \le i,j\le n-1 \).

Proof of lemma: First, \[ \prod_{0 \ne k} (1-\zeta^k) = f(1) = n, \] where \( f(x) = \frac{x^n-1}{x-1} = x^{n-1}+x^{n-2} + \cdots + 1.\) Next, note that \( \prod_{i \ne j} (\zeta^i-\zeta^j) \) for fixed \( i \) equals \( \zeta^i \) times \( n \), by factoring out a \( \zeta^i \) and using the above identity. So the whole product equals \[ n \cdot (\zeta n) \cdot (\zeta^2 n) \cdots (\zeta^{n-1} n) = \zeta^{n(n-1)/2} n^n, \] and \( \zeta^{n(n-1)/2} = \pm 1 \). This proves the lemma. \(_\square\)

Now we show that \( \Phi_n(x) \) is irreducible by reducing it to the following result:

If an integer-coefficient polynomial \( f(x) \) divides \( x^n-1 \) and \( \zeta \) is a root of \( f(x) \), then so is \( \zeta^p \) for any prime \( p \nmid n \).

Once this result has been proved, the irreducibility of \( \Phi_n(x) \) follows, because any integer-coefficient factor \(f(x)\) of \( \Phi_n(x) \) with a root \( \zeta \) must have all the rest of the primitive roots as well, by repeatedly applying the result.

Proof of result: Suppose \( \zeta^p \) is not a root. Then \( f(\zeta^p)\) is nonzero, and is a product of differences of \(n^\text{th}\) roots of unity. So it divides the giant product from the lemma, and thus must divide \( \pm n^n \); that is, \( \dfrac{n^n}{f(\zeta^p)} \) is an algebraic integer.

But \( f(x^p) \equiv f(x)^p \) mod \( p \) \(\big(\)because the binomial coefficients \( \binom{p}{i} \) are all divisible by \( p \) for \( 1 \le i \le p-1\big),\) so \( p\) divides \( f(\zeta^p) \) because \( f(\zeta)^p =0\). That is, \( \frac{f(\zeta^p)}p \) is an algebraic integer.

Putting these two together, we get \( \frac{n^n}p \) is an algebraic integer. But this is a rational number, so it must be an integer. This is a contradiction since \( p\nmid n\). \(_\square\)