For any given positive integer \(n\), a number \(a\) (which may be complex) is said to be a primitive \(n\)th root of unity if \(a^n = 1\) and there is no integer \(m\) such that \(0 < m < n\) and \(a^m = 1\). Write down the two primitive 4th roots of unity.
Let \(\mathrm{C}_n(x)\) be the polynomial such that the roots of the equation \(\mathrm{C}_n(x) = 0\) are the primitive \(n\)th roots of unity, the coefficient of the highest power of \(x\) is one and the equation has no repeated roots. Show that \(\mathrm{C}_4(x) = x^2 + 1\).
Find \(\mathrm{C}_1(x)\), \(\mathrm{C}_2(x)\), \(\mathrm{C}_3(x)\), \(\mathrm{C}_5(x)\) and \(\mathrm{C}_6(x)\), giving your answers as unfactorised polynomials.
Find the value of \(n\) for which \(\mathrm{C}_n(x) = x^4 + 1\).
Given that \(p\) is prime, find an expression for \(\mathrm{C}_p(x)\), giving your answer as an unfactorised polynomial.
Prove that there are no positive integers \(q\), \(r\) and \(s\) such that \(\mathrm{C}_q(x) \equiv \mathrm{C}_r(x)\,\mathrm{C}_s(x)\).
The hook
The \(n\)th roots of unity, the solutions of \(z^n = 1\), sit at the vertices of a regular \(n\)-gon. But they are not all alike. Among the \(12\)th roots of unity, for instance, \(1\) is already a first root of unity, \(-1\) is a square root of unity, \(\mathrm{i}\) is a fourth root, and only four of the twelve, the primitive ones, need all twelve steps to get back to \(1\).
Sorting the roots of unity by the number of steps they need, and building a polynomial from each class, produces the cyclotomic polynomials (“circle-dividing”, from the Greek). They are the basic building blocks of \(z^n - 1\), in the same way that primes are the building blocks of whole numbers, and they lie behind Gauss’s construction of the regular \(17\)-gon (Section 6.2), the roots-of-unity filter (Section 5.2) and a good deal of modern number theory.
Before you start
Every \(n\)th root of unity satisfies \(z^n = 1\). But the smallest positive power that gives \(1\) might be less than \(n\). For each of the four 4th roots of unity, \(1\), \(\mathrm{i}\), \(-1\), \(-\mathrm{i}\), what is that smallest power?
\(1^1 = 1\), \((-1)^2 = 1\), and \(\mathrm{i}^4 = (-\mathrm{i})^4 = 1\) with no smaller power working. So the smallest powers are \(1\), \(4\), \(2\), \(4\). This smallest power is called the order of the root of unity, and the primitive \(n\)th roots of unity are exactly those of order \(n\). The key fact for the whole question is that every root of unity has exactly one order.
Working it through
Stage 1 The first few
The primitive 4th roots are \(\mathrm{i}\) and \(-\mathrm{i}\), so \(\mathrm{C}_4(x) = (x - \mathrm{i})(x + \mathrm{i}) = x^2 + 1\).■
Which roots of unity have order \(1\), \(2\), \(3\), \(5\) and \(6\)? (Draw the \(6\)th roots of unity and sort them by order.)
Order \(1\): just \(1\), so \(\mathrm{C}_1(x) = x - 1\). Order \(2\): just \(-1\), so \(\mathrm{C}_2(x) = x + 1\).
Order \(3\): the cube roots of unity other than \(1\), that is, the roots of \(\frac{x^3 - 1}{x - 1}\). So \(\mathrm{C}_3(x) = x^2 + x + 1\).
Order \(5\): the fifth roots other than \(1\), which are the roots of \(\frac{x^5 - 1}{x - 1}\), so \(\mathrm{C}_5(x) = x^4 + x^3 + x^2 + x + 1\).
Order \(6\): of the sixth roots \(e^{k\pi\mathrm{i}/3}\), \(k = 0, \ldots, 5\), those with \(k = 0\), \(3\) have orders \(1\), \(2\), and \(k = 2\), \(4\) have order \(3\). That leaves \(e^{\pm\pi\mathrm{i}/3}\), so \[\mathrm{C}_6(x) = (x - e^{\mathrm{i}\pi/3})(x - e^{-\mathrm{i}\pi/3}) = x^2 - 2x\cos\tfrac\pi3 + 1 = x^2 - x + 1. \qed\]
Stage 2 Which \(n\) gives \(x^4 + 1\)?
The roots of \(x^4 + 1 = 0\) satisfy \(x^4 = -1\), so \(x^8 = 1\) but \(x^4 \neq 1\). Their order divides \(8\) but not \(4\), so it is \(8\). Conversely, a root of order \(8\) satisfies \(x^8 = 1\), \(x^4 \neq 1\), so \(x^4 = -1\). There are four primitive \(8\)th roots and four roots of \(x^4 + 1\), so \(n = 8\).■
Stage 3 Primes
If \(p\) is prime, the order of a \(p\)th root of unity divides \(p\), so it is \(1\) or \(p\). Every \(p\)th root except \(1\) is therefore primitive, and \[\mathrm{C}_p(x) = \frac{x^p - 1}{x - 1} = x^{p-1} + x^{p-2} + \cdots + x + 1. \qed\]
Stage 4 No cyclotomic polynomial is a product of two others
Suppose \(\mathrm{C}_q = \mathrm{C}_r\mathrm{C}_s\). Take a root of \(\mathrm{C}_r\). What is its order? What does the identity say about its order? What does that force?
Every root of \(\mathrm{C}_r\) (there is at least one, since \(e^{2\pi\mathrm{i}/r}\) is primitive) is a root of \(\mathrm{C}_r\mathrm{C}_s = \mathrm{C}_q\), so it has order \(q\). But it also has order \(r\), and a root of unity has only one order, so \(r = q\). Then \(\mathrm{C}_q = \mathrm{C}_q\,\mathrm{C}_s\), and since \(\mathrm{C}_q\) is not the zero polynomial, \(\mathrm{C}_s = 1\). That is impossible, because \(\mathrm{C}_s\) has at least one root, \(e^{2\pi\mathrm{i}/s}\). So no such \(q\), \(r\), \(s\) exist.■
Looking back
Sort by order. Every root of unity has a unique order, and grouping by order splits the roots of \(z^n - 1\) into disjoint classes.
Define a polynomial by its roots. Each \(\mathrm{C}_n\) was pinned down by saying exactly which numbers are its roots.
Uniqueness gives impossibility. Part (iv) needed only one idea: a root cannot have two different orders.
What’s really going on
Every \(n\)th root of unity has some order \(d\) that divides \(n\), and every \(d\)th root of unity of order \(d\) is an \(n\)th root of unity when \(d \mid n\). So the roots of \(x^n - 1\) split into classes by order, giving \[x^n - 1 = \prod_{d \mid n}\mathrm{C}_d(x).\] For example \(x^6 - 1 = \mathrm{C}_1\mathrm{C}_2\mathrm{C}_3\mathrm{C}_6 = (x - 1)(x + 1)(x^2 + x + 1)(x^2 - x + 1)\). Figure 6.1.1 shows the twelve \(12\)th roots of unity sorted in this way. The number of primitive \(n\)th roots, which is the degree of \(\mathrm{C}_n\), is the number of \(k\) between \(1\) and \(n\) with no common factor with \(n\): Euler’s totient function \(\varphi(n)\). Comparing degrees gives the identity \(\sum_{d \mid n}\varphi(d) = n\).
Integer coefficients, and a surprise
It is not obvious from the definition, but every cyclotomic polynomial has integer coefficients. (Use the factorisation of \(x^n - 1\) and induction: \(\mathrm{C}_n\) is \(x^n - 1\) divided by a product of earlier cyclotomic polynomials, and long division of integer polynomials by monic integer polynomials keeps the coefficients integers.) For a long time all known examples had coefficients \(0\), \(1\) and \(-1\). The first exception is \(\mathrm{C}_{105}\), which contains the term \(-2x^7\), found by Migotti in 1883; \(105 = 3 \times 5 \times 7\) is the smallest number with three distinct odd prime factors. In fact the coefficients of cyclotomic polynomials can be made as large as you like.
Irreducibility
Part (iv) shows that no cyclotomic polynomial is a product of two others. Something much stronger is true: \(\mathrm{C}_n\) cannot be factorised at all into polynomials with rational coefficients of lower degree. Gauss proved this for prime \(n\) (it follows from Eisenstein’s criterion, which you will meet in a first algebra course), and Kronecker and Dedekind for general \(n\). This irreducibility is what makes the cyclotomic polynomials the “primes” among polynomials related to roots of unity, and it is the starting point for the Galois theory of roots of unity.
The thinking skill
Sort the objects in a problem into classes with a single, well-defined invariant, and build structure class by class.
Here the invariant was the order of a root of unity. Because each root has exactly one order, the classes do not overlap, and \(x^n - 1\) splits as a product over them. The same pattern (a unique invariant giving a disjoint decomposition) underlies prime factorisation and the classification of finite abelian groups.
Try this next
Check the factorisation. Verify that \((x - 1)(x + 1)(x^2 + x + 1)(x^2 - x + 1) = x^6 - 1\), and that \(x^{12} - 1\) factorises as in Figure 6.1.1.
Twice a prime. Show that if \(p\) is an odd prime then \(\mathrm{C}_{2p}(x) = \mathrm{C}_p(-x)\). Check this for \(p = 3\).
Totients. Show that \(\varphi(p^k) = p^k - p^{k-1}\) for a prime \(p\), and that \(\mathrm{C}_{p^k}(x) = \mathrm{C}_p\bigl(x^{p^{k-1}}\bigr)\). Use this to find \(\mathrm{C}_9\).
A longer one. harder Using \(x^{15} - 1 = \mathrm{C}_1\mathrm{C}_3\mathrm{C}_5\mathrm{C}_{15}\), show that \(\mathrm{C}_{15}(x) = x^8 - x^7 + x^5 - x^4 + x^3 - x + 1\).
Further reading
Ian Stewart, Galois Theory (CRC Press). The standard undergraduate introduction; cyclotomic polynomials and the regular polygon appear early.
Harold Davenport, The Higher Arithmetic (Cambridge University Press). Includes roots of unity and their arithmetic.
Marcus du Sautoy, Finding Moonshine (Fourth Estate). A popular account of symmetry and group theory, including the story of Galois.