# The Cyclotomic polynomial

After we’ve met the terms of roots of unity, primitive roots, and deduced a great identity, we are now finally ready to define the Cyclotomic polynomial of order $n$. It is the polynomial where it’s roots are the primitive roots of unity of order $n$:

\Phi_n(x)=\prod_{\overset{1\leq k < n}{\text{gcd}(k,n)=1}} (x-\rho_n^k)

Let’s find out what’s so special about it:

First, note that it divides the polynomial $x^n-1$, since we can write it as:

x^n-1=\prod_{k=0}^{n-1}(x-\rho_n^k)=(x-1)(x-\rho_n)(x-\rho_n^2)\cdots (x-\rho_n^{n-1})

But we can conclude something stronger, there is a reason for why I have shown the disjoint decomposition in the last post:

\Omega_n=\bigcup_{d|n}\Omega_d^*

(Recall that $\Omega_n$ is the group of roots of unity of order $n$ and $\Omega_d^*$ is the set of the primitive roots of order $d$) This fact allows us to write the product a bit different:

\overbrace{\prod_{k=0}^{n-1}(x-\rho_n^k)}^{\Omega_n}=\prod_{d|n}\overbrace{\prod_{\overset{1\leq k< d}{(k,d)=1}}(x-\rho_d^k)}^{\Omega_d^{*}}

Pause and ponder on it for a second – make sure that’s clear, since that’s the major key here.

Now, note that the product:

\prod_{\overset{1\leq k< d}{(k,d)=1}}(x-\rho_d^k)

is exactly the definition of the cyclotomic polynomial of order $d$. Therefore:

\prod_{d|n}\prod_{\overset{1\leq k< d}{(k,d)=1}}(x-\rho_d^k)=\prod_{d|n}\Phi_d(x)

And in total we get that:

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

Now it’s pretty clear that the cyclotomic polynomial divides $x^n-1$, Moreover, we got a recursive definition for it:

x^n-1=\prod_{d|n}\Phi_d(x)=\Phi_n(x)\prod_{\overset{d< n}{d|n}}\Phi_d(x) \\
\\ \Downarrow \\
\Phi_n(x)=\frac{x^n-1}{\prod_{\overset{d< n}{d|n}}\Phi_d(x)}

That’s just great fact:

Note that $\Phi_1(x)=x-1$, and by this fact we can easily calculate the rest of them using with recursion that can be easily implemented in code (it may not be so efficient, but it works)

In addition, since $\Phi_1,x^n-1\in\mathbb{Q}$ we can easily prove by induction that $\Phi_n\in\mathbb{Q}[x]$ for every $n$:

The case $n=1$ is trivial. Now suppose that $n>1$ and for every $k, $\Phi_k\in\mathbb{Q}$. Therefore, the quotient:

\frac{\overbrace{x^n-1}^{\in\mathbb{Q}[x]}}{\underbrace{\prod_{\overset{d< n}{d|n}}\Phi_d(x)}_{\in\mathbb{Q}[x]}}

is a raitonal function in $\mathbb{Q}(x)$, however, this quotient is exactly $\Phi_n$, which is polynomial, therefore, the quotient is a polynomial with rational coefficents, so $\Phi_n\in\mathbb{Q}[x]$ as well.

## Surprising fact

Let’s calculate the first 5 cyclotomic polynomials:

\Phi_1(x)= x-1\\
\text{}\\
\Phi_2(x)= \frac{x^2-1}{x-1}=x+1\\
\text{}\\
\Phi_3(x)= \frac{x^3-1}{x-1}=x^2+x+1\\
\text{}\\
\Phi_4(x)= \frac{x^4-1}{(x-1)(x+1)}=\frac{x^4-1}{x^2-1}=x^2+1\\
\text{}\\
\Phi_5(x)= \frac{x^5-1}{x-1}=x^4+x^3+x^2+x+1\\

That’s pretty interesting… Not only that the coefficients are rationals, but they are integers, maybe it’s not a coincidence, maybe for every $n\in\mathbb{N}$:

\Phi_n\in\mathbb{Z}[x]

So as it turns out, it’s true! The cyclotomic polynomials have integer coefficients! That’s incredible! Think about it, that’s not a trivial fact at all! In order to prove it, I want to present Gauss’s lemma:

## Gauss’s lemma

So Gauss’s lemma is actually not just one lemma, but two. The first lemma deals with the term of a primitive polynomial – which is a polynomial where the greatest common divisor of it’s coefficients is one. For example the polynomial:

3x^2+6x+9

Is not primitive, since the GCD of it’s coefficients is 3 (=$\text{gcd}(3,6,9)$). However, the polynomial

x^2+10x+15

is primitive. It is a monic polymonial – it’s leading coefficient is one, so the GCD of the coefficients has to be one.

Ok, so the first part of the lemma states:

If $f,g\in\mathbb{Z}[x]$ are primitive polynomials, then their product is also primitive

And the second part states:

If $f\in\mathbb{Z}[x]$ is reducible over the rationals, then it is also reducible over the integers

I am not going to prove the lemmas here, since they are realted to ring theory, and I’ll prove them in a separate post related to ring theory, though the proofs are pretty short.

Now I am going to use the first part of the lemma to prove a statement which from it, it will follow immideatly that the cyclotomic polynomials have integer coefficients.

#### The statement

Suppose that $f(x)\in\mathbb{Z}[x]$ is a monic polynomial, and there exist two polynomials $g(x),h(x)\in\mathbb{Q}[x]$ such that:

f(x)=g(x)h(x)

Then $g(x),h(x)\in\mathbb{Z}[x]$.

##### The proof

The key here is to note that for every polynomial $r(x)$ with rational coefficients, there exists some rational number $a\in\mathbb{Q}$, such that $a\cdot r(x)$ has integer coefficients and it is primitive.

Why? We can actually construct one in two steps:

First, multiply the polynomial by the common denominator of it’s coefficients. For example:

r(x)=\frac{1}{3}x^2+\frac{1}{6}x+\frac{1}{4} \ \ \ \ /\cdot 24 \\ \Downarrow \\
24\cdot r(x)=8x^2+4x+6

Now, we can divide the new polynomial by the GCD of it’s coefficients – this yields a primitive polynomial. In our example, the GCD is 2, hence:

\frac{24}{2}\cdot r(x)=4x^2+2x+3

And $\frac{24}{2}=12$ is the number we were looking for.

So after we understand that, let $a_g,a_h$ be the rational numbers such that $a_g\cdot g(x), a_h\cdot h(x)$ are polynomials with integer coefficients and are also primitive. Therefore, by Gauss’s lemma, their product:

a_g g(x)\cdot a_hh(x)=a_ga_h\cdot g(x)h(x) \in\mathbb{Z}[x]

Is a primitive polynomial as well.

Recall that $g(x)h(x)=f(x)$ and $f$ is monic, hence the leading coefficient of $a_ga_h\cdot g(x)h(x)$ is $a_ga_h$. But we know that this is a polynomial with integer coefficients, so $a_ga_h$ is an integer.

Therefore, $a_g a_h$ is a common divisor of the coefficients of the product! Hence, it must be $\pm 1$ (since it divides the GCD, which is one):

a_ga_h=\pm 1 \\ \Downarrow \\
a_g=\pm1, a_h=\pm 1

Therefore:

\pm g(x), \pm h(x)\in\mathbb{Z}[x] \\ \Downarrow \\
g(x),h(x)\in\mathbb{Z}[x]

As we wanted!

## Back to the cyclotomic polynomial

We know that:

\Phi_n(x)=\frac{x^n-1}{\prod_{\overset{d< n}{d|n}}\Phi_d(x)}


Which is the same as:

\overbrace{x^n-1}^{\in\mathbb{Z}[x]\text{ and monic}}=\overbrace{\Phi_n(x)}^{\in\mathbb{Q}[x]}\cdot \overbrace{\prod_{\overset{d< n}{d|n}}\Phi_d(x)}^{\mathbb{Q}[x]}


And this fits perfrectly to what we just proved, hence $\Phi_n\in\mathbb{Z}[x]$ as we thought!

## Is it irreducible?

Our only goal left now is to find out if $\Phi_n$ is irreducible or not. If it is, then it is the minimal polynomial of $\rho_n$ over $\mathbb{Q}$, and this fact allows us to finally start talking about Galois theory related things (like what?)

#### Let’s find out

I am going to prove that it is indeed irreducible, but before I’ll do so, I want to mention few things that we’ll use in the proof:

###### Primitive root to the power of a prime number

First, note that if $\rho$ is a primitive root of unity of order $n$,so for any prime $p$ that doesn’t divide $n$, $\rho^p$ is also a primitive root of unity:

Suppose not, then there exists some $1\leq r such that:

(\rho^p)^r=\rho^{pr}=1=(\rho^{n})^m=\rho^{nm}\ \text{  for every }m\in\mathbb{N}

So there exists some $m\in\mathbb{N}$ such that $pr=nm$

Recall that $r$ is a divisor of $n$ (lagrange’s theorem…) so there exists some $k\in\mathbb{N}$ such that:

n=kr \\ \Downarrow \\
pr=nm=kr\cdot m  \ /:r \\
\\ \Downarrow \\
p=km

But $p$ is prime, so $k=1$ or $m=1$. If $k=1$, then $n=r$, and that’s a contradiction to $r$ being smaller than $n$. If $m=1$, then $p=k$, and we get that $n=k\cdot r=p\cdot r$ and that’s a contradiction since $p$ doesn’t divide $n$.

Therefore, no such $r$ exists, and $\rho^p$ is indeed a primitive polynomial.

###### Polynomial over $\mathbb{F}_p$$\mathbb{F}_p$

Recall that over the field $\mathbb{F}_p$, the identity $(a+b)^p=a^p+b^p$ is true. Moreover, by fermat’s little theorem, for every $a\in\mathbb{F}_p$: $a^p=a$ over $\mathbb{F}_p$. Therefore, if $h$ is a polynomial, then, over $\mathbb{F}_p$:

\overline{h}(x^p)=(x^k)^p+a_{n-1}(x^{k-1})^p+\cdots +a_0\overset{\text{Fermat}}{=}(x^k)^p+a_{n-1}^p(x^{k-1})^p+\cdots +a_0^p
= (x^k)^p+(a_{n-1}x^{k-1})^p+\cdots +a_0^p\overset{(a+b)^p}{=}(x^k+a_{n-1}x^{k-1}+\cdots a_0)^p=(\overline{h}(x))^p

And that’s a useful property we will use in the proof.

###### Separablility of $x^n-1$$x^n-1$ over $\mathbb{F}_p$$\mathbb{F}_p$

Recall that we’ve proved in this post that if the derivative of $f$ is not 0 over a field $F$, then it is separable over $F$.

So let’s see if $x^n-1$ is separable over $\mathbb{F}_p$, where $p$ doesn’t divide $n$:

(x^n-1)^\prime=\underbrace{n}_{(n,p)=1}\cdot x^{n-1}\neq 0\in\mathbb{F}_p

So it is indeed separable over $\mathbb{F}_p$.

#### The proof

Aimining for contradiction. suppose that $\Phi_n$ is reducible over $\mathbb{Q}$, so by the second part of Gauss’s lemma, it is also reducible over $\mathbb{Z}$.

Now, let $g,h\in\mathbb{Z}[x]$ be polynomials such that:

\Phi_n(x)=g(x)h(x)

And we can pick them both to be monic, and we can also also assume that $g$ is irreducible (why?)

Note that Some primitve roots of unity of order $n$ are roots of $g$, and the others are roots of $h$.

Let $\rho$ be a root of $g$, and let $p$ be any prime that doesn’t divide $n$. Note that $\rho^p$ is also a primitive root by what we’ve proved above. Now there are two cases:

#### For every such $p$$p$, $\rho^p$$\rho^p$ is a root of $g$$g$

Then we can conclude that every $a$ such that $(a,n)=1$, $\rho^a$ must be a root of $g$ as well:

Indeed, we can write $a=p_1\cdots p_k$ where the $p_i$-s are primes that doesn’t divide $n$ (if some of them divide $n$, then $a,n$ have a common factor). So, $\rho^{p_1}$ is a primitive root, and by the assumption of this case, it is a root of $g$.

Similarly, $(\rho^{p_1})^{p_2}$ is a root of $g$, and so on… Until we get that $(\rho^{p_1\cdots p_{k-1}})^{k}=\rho^a$ is a root of $g$.

Therefore, every primitive root of unity of order $n$ must be a root of $g$! so $\Phi_n(x)=g(x)$ (they have the same roots, and one divides the other) Moreover, by our assumption, $g$ is irreducible, then so as $\Phi_n$ as we wanted.

#### There exists some $p$$p$ where $\rho^p$$\rho^p$ is a root of $h$$h$

That is, $h(\rho^p)=0$, which is equivalent to $\rho$ being a root of the polynomial $h(x^p)$. However, $g$ is irreducible, thus, it is the minimal polynomial of $\rho$. So $g$ must divide $h(x^p)$. In other words, there exists some $r(x)\in\mathbb{Q}[x]$ such that:

h(x^p)=g(x)r(x)

However, $h(x^p)$ is monic, hence primitive with integer coefficients. So by the statement we proved, we know that $r(x)\in\mathbb{Z}[x]$, and now we can reduce the equation modulo $p$:

\overline{h}(x^p)=\overline{g}(x)\overline{r}(x) \ \ \ \text{ in }\mathbb{F}_{p}

However, we’ve seen that $\overline{h}(x^p)=(\overline{h}(x))^p$, thus:

(\overline{h}(x))^p=\overline{g}(x)\overline{r}(x) \ \ \ \text{ in }\mathbb{F}_{p}

Therefore, $\overline{h}(x)$ and $\overline{g}(x)$ have a common factor over $\mathbb{F}_p$ (you can decompose $(\overline{h}(x))^p$ into irrdeucible factors over $\mathbb{F}_p[x]$ since it is a UFD, so one factor must be a factor of $\overline{g}(x)$, but it is a factor of $\overline{h}(x)$ as well)

Now, note that

\overline{\Phi}_n(x)=\overline{g}(x)\overline{h}(x) \ \ \ \text{in }\mathbb{F}_p

But since $\overline{h}(x)$ and $\overline{g}(x)$ have a common factor, $\overline{\Phi}_n$ has a mutiple root over $\mathbb{F}_p$. However, it divides $\overline{x^n-1}$ over $\mathbb{F}_p$ so $\overline{x^n-1}$ has a mutiple root, but that’s a contradiction of it being separable.

Therefore, such case is impossible, hence, $\Phi_n$ is irreducible, as we wanted!

## The splitting field

Yes! Finally we’ve proved everything we wanted to prove about the cyclotomic polynomial. Now it’s time for some Galois theory:

It’s not hard to see that $\mathbb{Q}(\rho_n)$ is the splitting field of the cyclotomic polynomial, which is separable. Thus, the extension $\mathbb{Q}(\rho_n)/\mathbb{Q}$ is Galois. Moreover, it is a simple extension, and it’s degree is exactly the degree of the cyclotomic polynomial – $\varphi(n)$. Therefore, the order of the galois group is $\varphi(n)$ as well (Recall that $\varphi(n)$ is Euler totient function).

Since the roots of $\Phi_n$ are exactly the primitive roots of order $n$, and the automorphisms in the galois group does a permutation on the roots of $\Phi_n$, we can conclude that the automorphisms map a primitive root of unity to another primitive root of unity.

However, since the extension is simple, every automorphism is defined entirely by the image of $\rho_n$. Therefore, the automorphisms are exactly those of the form:

\sigma_k:\rho_n\mapsto \rho_n^k

Where $\rho_n^{k}$ is a primitive root of unity of order $n$ (in other words, $(k,n)=1$).

## The Galois group

Those facts allow us to fully identify the Galois group of the extension. We can define an isomorphism from Euler group of order $n$ – which is denoted as $U_n$ or $\mathbb{Z}_n^{\times}$, and defined as the set:

U_n=\{1\leq k< n:(k,n)=1\}

equipped with the action of multiplication modulo $n$ to $\text{Gal}(\mathbb{Q}(\rho_n)/\mathbb{Q})$

The isomorphism now is pretty clear:

f:U_n\to \text{Gal}(\mathbb{Q}(\rho_n)/\mathbb{Q})\\
k\mapsto \sigma_k

I won’t even bother proving that it is indeed an isomorphism…

Let’s see an exmaple:

## The extension $\mathbb{Q}(\rho_{12})/\mathbb{Q}$$\mathbb{Q}(\rho_{12})/\mathbb{Q}$

We’ve already seen what the roots of unity of $\rho_{12}$ are:

\color{purple}\rho_{12}^0=\rho_1=1\ (\text{order 1})
\\
\text{}\\
\color{blue} \rho_{12}^6=\rho_2=-1 \ (\text{order 2})
\\
\text{}\\
\color{green} \rho_{12}^{4}=\rho_3, \rho_{12}^{8}=\rho_3^2 \ (\text{order 3})
\\
\text{}\\
\color{orange} \rho_{12}^{3}=\rho_4, \rho_{12}^{9}=\rho_4^3 \ (\text{order 4})
\\
\text{}\\
\color{red} \rho_{12}^2=\rho_6, \rho_{12}^{10}=\rho_6^5 \ (\text{order 6})
\\
\text{}\\
\color{black}\rho_{12},\rho_{12}^5,\rho_{12}^7,\rho_{12}^{11} \ (\text{order 12})
\\

So $\varphi(12)=4$, and there are exactly $4$ automorphisms, and the group is of order 4. Well, there aren’t that much options for the group – it can one of the following:

\mathbb{Z}_4, V_4=\mathbb{Z}_2\times\mathbb{Z}_2

So all we have to do in order to deteremine which group it is exaclty, is to check whether or not $U_{12}$ is cyclic. We’ll the group is:

U_{12}=\{1,5,7,11\}

Let’s see if $5$ is a genarator:

5^1\equiv 5 \ (\text{mod }12)\\
5^2\equiv 25\equiv 1 \ (\text{mod }12)\\


So 5 is of order 2, similarly, 7 and 11 are both of order 2. Hence, the group is not cyclic, thus:

\text{Gal}(\mathbb{Q}(\rho_{12})/\mathbb{Q})\cong V_4

Let’s identify the roots as:

1\leftrightarrow \rho_{12} \\
\text{} \\
2\leftrightarrow \rho_{12}^{5} \\
\text{} \\
3\leftrightarrow \rho_{12}^{7}\\
\text{} \\
4\leftrightarrow \rho_{12}^{11}

We need to match each automorphism to a premutation – however, we can do it in clever way – note that each automorphism maps $\rho_{12}$ to one of the other roots. Since the automorphisms are all of order 2 (as elements of $V_4$), we have to map the image of $\rho_{12}$ back to $\rho_{12}$. The other two roots are being mapped to each other as well (why?). So the automorphisms are:

(1\ 2 )(3\ 4) \\
(1\ 3)(2\ 4) \\
(1\ 4)(2\ 3)

And the subgroup lattice is:

#### The sub-fields

Now we would like to calculate the sub-fields, and since the extension is galois – the subfields are all fixed fields.

Let’s start with $\sigma= (1\ 2)(3\ 4)$: Note that:

\sigma(\rho_{12}+\rho_{12}^5)=\sigma(\rho_{12})+\sigma(\rho_{12}^5)=\rho_{12}^5+\rho_{12} \\ \Downarrow \\
\rho_{12}+\rho_{12}^5\in\mathbb{Q}^{\langle (1\ 2)(3\ 4)\rangle}

Moreover:

\rho_{12}+\rho_{12}^5=(\cos {\frac{2\pi}{12}}+i\sin\frac{2\pi}{12})+(\cos {\frac{2\pi\cdot 5}{12}}+i\sin\frac{2\pi\cdot 5}{12})
=(\cos {\frac{\pi}{6}}+i\sin\frac{\pi}{6})+(\cos {\frac{5\pi}{6}}+i\sin\frac{5\pi}{6})
=(\cos {\frac{\pi}{6}}+\cos {\frac{5\pi}{6}})+i(\sin\frac{\pi}{6}+\sin\frac{5\pi}{6})

Recall that $\cos \theta = -\cos (\pi - \theta)$ and $\sin\theta =\sin(\pi - \theta)$. So:

=0+i(2\sin\frac{\pi}{6})=2\sin\frac{\pi}{6}\cdot i

And $\sin \frac{\pi}{6}$ is $\frac{1}{2}$:

Therefore, we conclude that:

\rho_{12}+\rho_{12}^5=i

So, in total we get that:

\mathbb{Q}(i)=\mathbb{Q}(\rho_{12}+\rho_{12}^{5})\sube \mathbb{Q}^{\langle (1\ 2)(3\ 4)\rangle}

However, by the fundamental theorem:

[\mathbb{Q}(i):\mathbb{Q}]{=}2=[V_4:\langle (1\ 2)(3\ 4)\rangle]\overset{\text{fund.thm.}}{=}[\mathbb{Q}^{\langle (1\ 2)(3\ 4)\rangle}:\mathbb{Q}]

Therefore, the fields (degrees) are the same and we conclude that:

\mathbb{Q}(i)= \mathbb{Q}^{\langle (1\ 2)(3\ 4)\rangle}

In a similar way we get that:

\mathbb{Q}(\sqrt{3})\overset{(\text{why?})}{=}\mathbb{Q}(\cos \frac{\pi}{6})=\mathbb{Q}^{\langle (1\ 4)(2\ 3)\rangle}

(Try it! Hint: check if the element $\rho_{12}+\rho_{5}$ is being fixed under the automorphism $(1\ 4))(2\ 3)$). For the fixed field $\mathbb{Q}^{\langle (1\ 3)(2\ 4)\rangle}$ we need to be a bit more creative – we’ll pick the element:

\rho_{12}^{}\cdot\rho_{12}^{7}=\rho_{12}^8

This one is indeed being fixed under the automorphism $(1\ 3)(2\ 4)$, moreover:

\rho_{12}^8=\cos\frac{2\pi\cdot 8}{12}+i\sin\frac{2\pi\cdot 8}{12}=\cos\frac{4\pi}{3}+i\sin\frac{4\pi}{3}
=-\cos\frac{\pi}{3}+i\sin\frac{\pi}{3}=-\frac{1}{2}+i\frac{\sqrt{3}}{2}

So:

\mathbb{Q}(\sqrt{3}i)=\mathbb{Q}(-\frac{1}{2}+i\frac{\sqrt{3}}{2})\sube\mathbb{Q}^{\langle (1\ 3)(2\ 4)\rangle}

And in a similar way to before, we can compare the degrees of the extensions and conclude that:

\mathbb{Q}(\sqrt{3}i)=\mathbb{Q}^{\langle (1\ 3)(2\ 4)\rangle}

That’s it!

Note that in fact, $\mathbb{Q}(\rho_{12})=\mathbb{Q}(\sqrt{3},i)$,

## Summary

Ok, so we’ve met the cyclotomic polynimial and the cyclotomic extensions. As we’ve seen, they have beautiful properties – they have integer coefficients, they are irreducible, and we can compute them recursively.

However, that’s not going to be the last time we’ll see them. As I said, those polynomials, and those extension are so useful – and that’s great, since I am huge fan of them!