# Notes on Cyclotomic Polynomial

(This is a work in progess...)

## Nth roots of Unity

$n^{th}$ roots of unity is given by the equation:
$\large (1)^{1\over n}=e^{i\frac{2k\pi}{n}}$, $\large k=0,1,\dots,n-1$

## Nth Cyclotomic Polynomial

$n^{th}$ cyclotomic polynomial, for any positive integer $n$, is the unique irreducible polynomial with integer coefficients that is a divisor of $x^{n}-1$ and is not a divisor of $x^{k}-1$ for any $k < n$.

Its roots are all $n^{th}$ primitive roots of unity $e^{2i\pi {\frac{k}{n}}}$, where $1\le k\le n$ and $k$ & $n$ are coprime.

$\large \Phi_{n}(x)=\prod_{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\left(x-e^{2i\pi {\frac {k}{n}}}\right)$

It may also be defined as the monic polynomial with integer coefficients that is the minimal polynomial  over the field of the rational numbers of any primitive $n$th-root of unity.

In short, $\Phi_{n}(x)|x^n-1$, but $\Phi_{n}(x)\not|x^k-1$, for $k=0,\dots,n-1$.

## Relation linking cyclotomic polynomials & primitive roots of unity

$\prod_{d\mid n}\Phi_{d}(x)=x^{n}-1$

That is,  $x$ is a root of $x^n - 1$ if and only if it is  a $d$th primitive roots of unity for some $d$ that divides $n$.

### GAP experiment to understand this relationship:

gap> x:=Indeterminate(Rationals,"x");
x
gap> C1:=CyclotomicPolynomial(Rationals,1);
x-1
gap> C2:=CyclotomicPolynomial(Rationals,2);
x+1
gap> C3:=CyclotomicPolynomial(Rationals,3);
x^2+x+1
gap> C4:=CyclotomicPolynomial(Rationals,4);
x^2+1
gap> C6:=CyclotomicPolynomial(Rationals,6);
x^2-x+1
gap> C12:=CyclotomicPolynomial(Rationals,12);
x^4-x^2+1
gap> (x^12-1)/C12;
x^8+x^6-x^2-1
gap> C1*C2*C3*C4*C6*C12;
x^12-1
gap> C1*C2*C3*C4*C6;
x^8+x^6-x^2-1

## Interesting fact:

While $\Phi_{n}(x)$ uses complex number in its definition, it produces irreducible polynomial over integer coefficients.
That is while $\Phi:\mathbb{Z}\to\mathbb{Z}$, it is defined using a $c\in\mathbb{C}$ in its definition.

Closer inspection reveals this is because of symmetry (look at the applet for nth root). One of the root will always be $1$, and when $n$ is even there is another root which is $-1$. The other roots will be conjugate of each other in pairs.
And when $n$ is odd one of the $nth$ root will be $1$, while other roots occurring as conjugates in pairs.

When you multiply or add two complex conjugates, it always produces real numbers.  (Incomplete...).

## When n is prime:

If $n$ is a prime number, then
$\Phi_{n}(x)=1+x+x^{2}+\cdots +x^{n-1}$
$=\sum_{k=0}^{n-1}x^{k}$.

If $n = 2p$ where $p$ is an odd prime number, then
$\Phi_{2p}(x)=1-x+x^{2}-\cdots +x^{p-1}$
$=\sum_{k=0}^{p-1}(-x)^{k}$.

## Cyclotomic Polynomials upto n=41

$\Phi_{1}(x)=x-1$

$\Phi_{2}(x)=x+1$

$\Phi_{3}(x)=x^{2}+x+1$

$\Phi_{4}(x)=x^{2}+1$

$\Phi_{5}(x)=x^{4}+x^{3}+x^{2}+x+1$

$\Phi_{6}(x)=x^{2}-x+1$

$\Phi_{7}(x)=x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1$

$\Phi_{8}(x)=x^{4}+1$

$\Phi_{9}(x)=x^{6}+x^{3}+1$

$\Phi_{10}(x)=x^{4}-x^{3}+x^{2}-x+1$

$\Phi_{11}(x)=x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1$

$\Phi_{12}(x)=x^{4}-x^{2}+1$

$\Phi_{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$

$\Phi_{14}(x)=x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1$

$\Phi_{15}(x)=x^{8}-x^{7}+x^{5}-x^{4}+x^{3}-x+1$

$\Phi_{16}(x)=x^{8}+1$

$\Phi_{17}(x)=x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1$

$\Phi _{18}(x)=x^{6}-x^{3}+1$

$\Phi_{19}(x)=x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1$

$\Phi_{20}(x)=x^{8}-x^{6}+x^{4}-x^{2}+1$

$\Phi _{21}(x)=x^{12}-x^{11}+x^{9}-x^{8}+x^{6}-x^{4}+x^{3}-x+1$

$\Phi _{22}(x)=x^{10}-x^{9}+x^{8}-x^{7}+x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1$

$\Phi _{23}(x)=x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1$

$\Phi_{24}(x)=x^{8}-x^{4}+1$

$\Phi_{25}(x)=x^{20}+x^{15}+x^{10}+x^{5}+1$

$\Phi_{26}(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$

$\Phi_{27}(x)=x^{18}+x^{9}+1$

$\Phi _{28}(x)=x^{12}-x^{10}+x^{8}-x^{6}+x^{4}-x^{2}+1$

$\Phi _{29}(x)=x^{28}+x^{27}+x^{26}+x^{25}+x^{24}+x^{23}+x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1$

$\Phi _{30}(x)=x^{8}+x^{7}-x^{5}-x^{4}-x^{3}+x+1$

$\Phi _{31}(x)=x^{30}+x^{29}+x^{28}+x^{27}+x^{26}+x^{25}+x^{24}+x^{23}+x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1$

$\Phi _{32}(x)=x^{16}+1$

$\Phi _{33}(x)=x^{20}-x^{19}+x^{17}-x^{16}+x^{14}-x^{13}+x^{11}-x^{10}+x^9-x^7+x^6-x^4+x^3-x+1$

$\Phi _{34}(x)=x^{16}-x^{15}+x^{14}-x^{13}+x^{12}-x^{11}+x^{10}-x^{9}+x^{8}-x^{7}+x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1$

$\Phi _{35}(x)=x^{24}-x^{23}+x^{19}-x^{18}+x^{17}-x^{16}+x^{14}-x^{13}+x^{12}-x^{11}+x^{10}-x^{8}+x^{7}-x^{6}+x^{5}-x+1$

$\Phi_{36}(x)=x^{12}-x^{6}+1$

$\Phi_{37}(x)=x^{36}+x^{35}+x^{34}+x^{33}+x^{32}+x^{31}+x^{30}+x^{29}+x^{28}+x^{27}+x^{26}+x^{25}+x^{24}+x^{23}+x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1$

$\Phi_{38}(x)=x^{18}-x^{17}+x^{16}-x^{15}+x^{14}-x^{13}+x^{12}-x^{11}+x^{10}-x^{9}+x^{8}-x^{7}+x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1$

$\Phi_{39}(x)=x^{24}-x^{23}+x^{21}-x^{20}+x^{18}-x^{17}+x^{15}-x^{14}+x^{12}-x^{10}+x^{9}-x^{7}+x^{6}-x^{4}+x^{3}-x+1$

$\Phi_{40}(x)=x^{16}-x^{12}+x^{8}-x^{4}+1$

$\Phi_{41}(x)=x^{40}+x^{39}+x^{38}+x^{37}+x^{36}+x^{35}+x^{34}+x^{33}+x^{32}+x^{31}+x^{30}+x^{29}+x^{28}+x^{27}+x^{26}+x^{25}+x^{24}+x^{23}+x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1$