### Introduction

The word "Cyclotomy" literally means "cutting a circle". So the subtitle of the post suggests that the post is going to be about some polynomials which are related to cutting a circle. Cutting a circle actually refers to dividing a given circle into a number of arcs of same length. Supposing that we are able to divide a given circle into, say $ n$, arcs of equal length by means of points $ P_{0}, P_{1}, \ldots, P_{n - 1}$ then joining the adjacent points we obtain a regular polygon $ P_{0}P_{1}\ldots P_{n - 1}$ of $ n$ sides. Therefore cyclotomic polynomials are somehow related to the construction of regular polygons.In the previous post about complex numbers, we were able to establish that construction of a regular polygon of $ n$ sides requires finding complex numbers $ z$ such that $ z^{n} = 1$. Thus we need to solve the equation $$z^{n} - 1 = 0\tag{1}$$ One trivial solution is $ z = 1$, but we are rather interested in solutions other than $ z = 1$. All the solutions of the above equation are said to be

*$ n^{th}$ roots of unity*. So how do we go about finding these $ n^{th}$ roots of unity?

Obviously we need to factorize the expression $ z^n - 1$ and then find any linear factors if possible. For $ n = 4$ we can proceed as follows: \begin{align} &z^4 - 1 = 0\notag\\ &\Rightarrow (z^2 - 1)(z^2 + 1) = 0\notag\\ &\Rightarrow (z - 1)(z + 1)(z^2 + 1) = 0\notag\\ &\Rightarrow z = 1,\,\, z = -1,\,\, z^2 + 1 = 0\notag\\ &\Rightarrow z = 1,\,\,z = -1,\,\,z^2 = -1\notag\\ &\Rightarrow z = 1,\,\,z = -1,\,\,z = i,\,\,z = -i\notag \end{align} Therefore we see that factorization of the polynomial $ z^{n} - 1$ is the key to finding $ n^{th}$ roots of unity. This is exactly where

*cyclotomic polynomials*come into play. Cyclotomic polynomials are the irreducible factors of the polynomial $ z^{n} - 1$. More precisely we have the following definition:

*For any given positive integer $ n$, the $ n^{th}$ cyclotomic polynomial, denoted by $ \Phi_{n}(z)$, is that irreducible factor (over field of rationals) of polynomial $ z^{n} - 1$ which is not a factor of any polynomial $ z^{m} - 1$ where $ m < n$.*

(

*Note to the not so casual reader:*It will be proved later in this post that there will be one and only one such irreducible factor which is not the factor of any $ z^{m} - 1$ with $ m < n$.)

For $ n = 1$, it is clear that $ \Phi_{1}(z) = z - 1$. For $ n = 2$, we have $$ z^{2} - 1 = (z - 1)(z + 1)$$ and since $ (z - 1)$ is already used up in factorization for case $ n = 1$, $ \Phi_{2}(z) = z + 1$.

For $ n = 3$, $ z^3 - 1 = (z - 1)(z^2 + z + 1)$ and the factor $ z^2 + z + 1$ is irreducible so that $ \Phi_{3}(z) = z^{2} + z + 1$. Similarly $ \Phi_{4}(z) = z^2 + 1$.

### Primitive $ n^{th}$ Roots of Unity

The complex number $ \zeta = \cos(2\pi / n) + i\sin(2\pi / n)$ is obviously an $ n^{th}$ root of unity since $$\zeta^{n} = \cos\left(n \cdot \frac{2\pi}{n}\right) + i\sin\left(n \cdot\frac{2\pi}{n}\right) = \cos(2\pi) + i\sin(2\pi) = 1$$ Now consider the powers of $ \zeta$. For each $ k, 0 \leq k < n, \zeta^{k}$ is also an $ n^{th}$ root of unity as $ (\zeta^{k})^{n} = (\zeta^{n})^{k} = 1^{k} = 1$. Also each of these powers of $ \zeta$ is distinct from another, i.e. $ \zeta^{l} \neq \zeta^{k}, 0\leq k, l < n$ if $ l \neq k$. Thus the numbers $ 1, \zeta, \zeta^{2}, \ldots, \zeta^{n - 1}$ are all the "n" $ n^{th}$ roots of unity.Consider any such $ n^{th}$ root say $ \zeta^{k}, 0 < k < n$. Obviously we have $$\zeta^{k} = \cos\left(\frac{2k\pi}{n}\right) + i\sin\left(\frac{2k\pi}{n}\right)$$ If $ k$ and $ n$ have a common factor we can reduce the fraction $ k / n$ into another fraction, say $ l / m$, where $ m < n,\, l < k$. Then it follows that $$\zeta^{k} = \cos\left(\frac{2l\pi}{m}\right) + i\sin\left(\frac{2l\pi}{m}\right)$$ is also an $ m^{th}$ root of unity for some $ m < n$. Clearly we are not interested in such repeated roots (i.e. they occur as smaller roots of unity), but would rather like to focus on those $ n^{th}$ roots of unity which are not the $ m^{th}$ roots of unity for any $ m < n$. These are obtained as $ \zeta^{k}$ where $ k$ and $ n$ do not have any common factor, i.e. when $ k$ is coprime to $ n$. Such $ n^{th}$ roots of unity are called

**the primitive $ n^{th}$ roots of unity**. What we have achieved above can be stated as follows:

**The primitive $ n^{th}$ roots of unity are $ \zeta^{k}$ where $ 1 \leq k < n$, $ k$ is coprime to $ n$ and**$$\zeta = \cos\left(\frac{2\pi}{n}\right) + i\sin\left(\frac{2\pi}{n}\right)$$ The number of positive integers $ k < n$ and coprime to $ n$ is denoted by $ \phi(n)$ and is called the

**Euler's totient function.**Also $ \phi(1)$ is defined to be $ 1$. Thus the number of primitive $ n^{th}$ roots of unity is $ \phi(n)$. From elementary number theory the following are easily deduced:

- $ \phi(mn) = \phi(m)\phi(n)$ if $ m$ is coprime to $ n$.
- $ \phi(p^{k}) = p^{k} - p^{k - 1}$ where $ p$ is a prime number.
- $ \displaystyle \phi(n) = n\left(1 - \frac{1}{p_{1}}\right)\left(1 - \frac{1}{p_{2}}\right)\cdots\left(1 - \frac{1}{p_{k}}\right)\,\,\,$ where $ p_{1}, p_{2}, \ldots, p_{k}$ are all the distinct prime factors of $ n$.

### Primitive $ n^{th}$ Roots and Cyclotomic Polynomials

Let us consider the polynomial $$P_{n}(z) = \prod_{1 \leq k \leq n, (k, n) = 1}(z - \zeta^{k})$$ where $ (k, n)$ refers to the GCD (greatest common divisor) of $ k$ and $ n$. Note that in the above expression $ \zeta$ can be taken as any of $ \phi(n)$ primitive roots (this is easy to establish if one understands the fact that the positive integers less than $ n$ and coprime to $ n$ form a group under modulo $ n$ multiplication). Thus the polynomial $ P_{n}(z)$ has as its roots all the primitive $ n^{th}$ roots of unity. We will now identify it with the cyclotomic polynomial $ \Phi_{n}(z)$ by proving that $ P_{n}(z)$ is an irreducible polynomial with integral coefficients.We first establish that

**$ P_{n}(z)$ has integer coefficients**. To do so we will establish the following: $$z^{n} - 1 = \prod_{d \mid n}P_{d}(z)\tag{2}$$ Since any $ n^{th}$ root of unity is of the form $$\cos\left(\frac{2k\pi}{n}\right) + i\sin\left(\frac{2k\pi}{n}\right)$$ and we can replace $ k / n$ with a fraction $ c / d$ in lowest terms so that $ d \mid n$, it follows that any $ n^{th}$ root of unity is a primitive $ d^{th}$ root of unity for some divisor $ d$ of $ n$ and vice-versa. Also if $ d_{1}$ and $ d_{2}$ are two distinct divisors of $ n$ then none of primitive $ d_{1}^{th}$ roots of unity is a primitive $ d_{2}^{th}$ root of unity. Thus the above factorization of $ (z^{n} - 1)$ as a product of polynomials $ P_{d}(z)$ is proved.

The above factorization (2) can be used to prove that $ P_{n}(z)$ has integer coefficients. Clearly $ P_{1}(z) = z - 1$ and we can apply induction by assuming that $ P_{k}(z)$ has integer coefficients for $ k < n$. Then we have $$P_{n}(z) = \frac{z^{n} - 1}{\prod\limits_{d \mid n,\, d < n}P_{d}(z)} = \frac{z^{n} - 1}{g(z)}$$ where $ g(z)$ is a polynomial with integer coefficients and leading coefficient $ 1$ (by induction hypothesis). It follows by Gauss Lemma that $ P_{n}(z)$ has integer coefficients.

We next establish that

**$ P_{n}(z)$ is irreducible over the field of rationals**.

The proof which follows is the one provided by Gauss and it uses modular arithmetic in very ingenious way. We will summarize the results needed as follows:

- For a given prime $ p$, the numbers $ 0, 1, 2, \ldots, (p - 1)$ form a finite field under the operations of modulo addition and multiplication modulo $ p$.
- Since these numbers form a field, say $ F_{p}$, we can talk about polynomials $ f(z)$ whose coefficients are in $ F_{p}$. The set of all such polynomials, say $ F_{p}[z]$, has the unique factorization property i.e. any such polynomial can be factored as a product of irreducible polynomials in $ F_{p}[z]$ in a unique way apart from the order of the factors. The proof is same as that used for normal polynomials with rational coefficients.
- If $ f(z)$ is a polynomial in $ F_{p}[z]$ then $ \{f(z)\}^{p} = f(z^{p})$. This is true for constant polynomials by Fermat's theorem which says that $ a^{p} \equiv a\,\,\text{mod} (p)$. For higher degree polynomials this is achieved by induction by writing $ f(z) = az^{n} + g(z)$ and using binomial theorem to raise both sides to power $ p$. In so doing we only need to note that the binomial coefficients involved are divisible by $ p$.

**proof of irreducibility of $ P_{n}(z)$**is done in two stages:

####
**Stage 1:**

Let $ \zeta$ be a primitive $ n^{th}$ root of unity and let $ f(z)$ be its minimal polynomial i.e. $ f(z)$ is monic (leading coefficient $ 1$), has rational coefficients and
irreducible and $ f(\zeta) = 0$. Since $ \zeta$ is also a root of $ z^{n} - 1 = 0$, it follows that $ f(z)$ divides $ (z^{n} - 1)$ and by Gauss Lemma $ f(z)$ has integer coefficients as well. We now establish the following:*If $ p$ is any prime which does not divide $ n$ then $ \zeta^{p}$ is a root of $ f(z) = 0$.*

*Proof:*Since $ \zeta$ is also a root of $ P_{n}(z) = 0$ it follows that $ f(z)$ divides $ P_{n}(z)$. Thus we have $ P_{n}(z) = f(z)g(z)$ where $ g(z)$ is also monic and has integer coefficients (by Gauss Lemma). Since $ p$ is coprime to $ n$ it follows that $ \zeta^{p}$ is also a primitive $ n^{th}$ root. And therefore $ P_{n}(\zeta^{p}) = 0$.

Assuming that $ \zeta^{p}$ is not a root of $ f(z) = 0$ (otherwise there is nothing to prove), we see that it must be a root of $ g(z) = 0$. Therefore $ \zeta$ is a root of $ g(z^{p}) = 0$. Since $ f(z)$ is the minimal polynomial of $ \zeta$, it follows that $ f(z)$ divides $ g(z^{p})$ so that $ g(z^{p}) = f(z)h(z)$ where $ h(z)$ is monic with integer coefficients. Also since $ P_{n}(z)$ is a factor of $ (z^n - 1)$ so that we have $ z^{n} - 1 = P_{n}(z)d(z)$ where $ d(z)$ is again monic with integer coefficients. We thus have the following equations: $$z^{n} - 1 = f(z)g(z)d(z)\tag{3}$$ $$g(z^{p}) = f(z)h(z)\tag{4}$$ We now apply the modulo $ p$ operation to each of the equations above, i.e. we replace each coefficient in the polynomials involved with its remainder when it is divided by $ p$. The resulting polynomials are all in $ F_{p}[z]$ and we will use the same letters to denote them. So the above equations are now to be interpreted as relations between some polynomials in $ F_{p}[z]$. The second equation can now be equivalently written as $$\{g(z)\}^{p} = f(z)h(z)\tag{5}$$ Let $ k(z)$ in $ F_{p}[z]$ be an irreducible factor of $ f(z)$. Then from the above equation (5), $ k(z)$ divides $ \{g(z)\}^{p}$ and so divides $ g(z)$. Thus from equation $(3)$ the polynomial $ \{k(z)\}^{2}$ divides $ (z^{n} - 1)$. Thus $ (z^n - 1)$ has repeated factors and therefore $ (z^{n} - 1)$ and its derivative $ nz^{n - 1}$ must have a common factor. Since $ n$ is coprime to $ p$, therefore the derivative $ nz^{n - 1}$ is non-zero polynomial and it clearly does not have any common factor with $ (z^{n} - 1)$.

We have reached a contradiction and therefore the initial assumption that $ \zeta^{p}$ is not the root of $ f(z) = 0$ is wrong. The result is now proved.

####
**Stage 2:**

We have thus established that if $ f(z)$ is the minimal polynomial for any primitive $ n^{th}$ root of unity then for any prime $ p$ not dividing $ n$, $ \zeta^{p}$ (which is again a primitive $ n^{th}$ root) is also a root of $ f(z) = 0$. And since $ f(z)$ is irreducible and monic, it will act as minimal polynomial for the primitive root $ \zeta^{p}$.The same logic can be applied repeatedly and we will get the result that $ f(z)$ is the minimal polynomial for $ \zeta^{p_{1}p_{2}\ldots p_{m}}$ where $ p_{1}, p_{2}, \ldots, p_{m}$ are any primes not dividing $ n$. It follows that $ \zeta^{k}$ where $ k$ is coprime to $ n$ is also a root of $ f(z)$. Thus all the primitive $ n^{th}$ roots of unity are roots of $ f(z) = 0$. Hence $ P_{n}(z)$ divides $ f(z)$. Since $ f(z)$ is irreducible it follows that $ f(z) = P_{n}(z)$ (both $ f(z)$ and $ P_{n}(z)$ are monic). We thus have established that $ P_{n}(z)$ is irreducible.

Moreover since the roots of $ P_{n}(z) = 0$ are not the roots of any $ z^{m} - 1 = 0$ for $ m < n$, it follows that $ P_{n}(z)$ is the irreducible factor of $ (z^{n} - 1)$ which is not the factor of any $ z^{m} - 1$ for $ m < n$. And thus by our definition of cyclotomic polynomials we have $ P_{n}(z) = \Phi_{n}(z)$. We have also justified the note about our definition of cyclotomic polynomials.

What we have achieved here can be summarized as:

**The roots of the polynomial equation $ \Phi_{n}(z) = 0$ are precisely the $ \phi(n)$ primitive $ n^{th}$ roots of unity.**

And thus the

**degree of $ \Phi_{n}(z)$ is $ \phi(n)$**. Also since $ \Phi_{n}(z)$ is irreducible, we get:

**$ \Phi_{n}(z)$ is the minimal polynomial for each of the primitive $ n^{th}$ roots of unity.**

The ground work in the theory of cyclotomic polynomials is now complete and we can then turn towards solving the cyclotomic equation $ \Phi_{n}(z) = 0$. The solution as provided by Gauss is beautiful, but somewhat involved and will therefore be divided into multiple posts.

**Print/PDF Version**

we can replace k/n with a fraction c/d in lowest terms so that d∣n, it follows that any nth root of unity is a primitive dth root of unity for some divisor d of n and vice-versa

I found this part hard to accept. I can accept the vice-versa part. Clearly, any dth root of unity is also an nth root of unity for some divisor d of n. But it is not true that any nth root of unity is a primitive dth root of unity. Take any nth root of unity, say for n= 15, k= 4. and let d be 5. Clearly, (Z^4)^5 is not equal to 1. I guess I must have misunderstood what you mean by replace the fraction. Would greatly appreciate an explanation

Kazbich-the-bandit

June 25, 2014 at 1:13 AMI am also finding difficulty understanding the divisors issue. Every number is a divisor of itself. If any nth root of unity is also a primitive dth root of some divisor of n, then how can it be true that d and n as distinct divisors of n do not share primitive roots. I assume that by any 'nth root' you also include the primitve nth roots. I wondered if by distinct divisor you meant coprime but that seemed improbable because you would have specified it if it were the case.

Kazbich-the-bandit

June 25, 2014 at 2:20 AM@Kazbich-the-bandit,

First we deal with "replacing $k/n$ with $c/d$" thing. Clearly this means that $k/n = c/d$ and $c, d$ are coprime to each other. We have thus reduced $k/n$ into lowest form $c/d$ and $c, d$ have no common factors. In your example $n = 15, k = 4$ so that $k/n = 4/15$ is already in lowest form and then $c = 4, d = 15$. Thus note that given $k, n$ the values $c, d$ are not arbitrary like you try to take $d = 5$.

Paramanand Singh

June 25, 2014 at 12:00 PM@Kazbich-the-bandit,

Let's now see your second issue. Suppose $d_{1}, d_{2}$ are two distinct divisors of $n$. Suppose $k, l$ are two integers such that $k$ is coprime to $d_{1}$ and $l$ is coprime to $d_{2}$. Then $(\cos(2\pi k/d_{1}) + i\sin(2\pi k/d_{1}))$ is a primitive $d_{1}^\text{th}$ root and similarly $(\cos(2\pi l/d_{2}) + i\sin(2\pi l/d_{2}))$ is a primitive $d_{2}^\text{th}$ root. If they are same then $k/d_{1} = l/d_{2}$. This is not possible unless $d_{1} = d_{2}$ and $k = l$ because the ratios $k/d_{1}$ and $l/d_{2}$ are in their lowest forms.

Paramanand Singh

June 25, 2014 at 1:07 PM