Cyclotomic polynomials

Cyclotomic (or "circle dividing") polynomials are the irreducible factors of $z^{n}-1\!$ when the polynomial coefficients are restricted to the field of rational numbers. For example

$z^{6}-1=(z^{2}-z+1)(z^{2}+z+1)(z+1)(z-1)$.

The cyclotomic polynomials are often written as $\Phi _{n}(z)$. The polynomial $z^{n}-1\!$ has exactly as many of these factors as there are integer divisors of n:

$z^{6}-1=\Phi _{6}(z)\Phi _{3}(z)\Phi _{2}(z)\Phi _{1}(z)$.

Finding cyclotomic polynomials

Recursive method

Cyclotomic polynomials are defined by the equation

$z^{n}-1=\prod _{d\,\mid \,n}\Phi _{d}(z)$.

Solving for $\Phi _{n}(z)$, one obtains

$\Phi _{n}(z)={\frac {z^{n}-1}{\prod _{(d\neq n)\,\mid \,n}\Phi _{d}(z)}}$.

One can then construct any polynomial recursively, given that $\Phi _{1}(z)=z-1$:

$\Phi _{2}(z)={\frac {z^{2}-1}{z-1}}=z+1$

$\Phi _{3}(z)={\frac {z^{3}-1}{z-1}}=z^{2}+z+1$

$\Phi _{6}(z)={\frac {z^{6}-1}{(z-1)(z+1)(z^{2}+z+1)}}=z^{2}-z+1$.

Direct method

For larger values of n, it is easier to use the direct formula, based on the Möbius inversion of the above formula:

$\Phi _{n}(z)=\prod _{d\,\mid n}(z^{n/d}-1)^{\mu (d)},$

where μ is the Möbius function. For example, one would follow these steps for n = 60:

1. Factor n.

$60=2^{2}*3*5$

2. Determine the square-free divisors of n, and classify them according to whether their number of prime factors are even or odd.

$30=2*3*5$ (Odd)

$15=3*5$ (Even)

$10=2*5$ (Even)

$6=2*3$ (Even)

$5=5$ (Odd)

$3=3$ (Odd)

$2=2$ (Odd)

$1=1$ (Even, since 1 is not a prime)

3. Form the factors $z^{n/d}-1$, putting the factors from the even class in the numerator and those from the odd class in the denominator.

$\Phi _{60}(z)={\frac {(z^{60}-1)(z^{10}-1)(z^{6}-1)(z^{4}-1)}{(z^{30}-1)(z^{20}-1)(z^{12}-1)(z^{2}-1)}}$

$={\frac {(z^{30}+1)(z^{2}+1)}{(z^{10}+1)(z^{6}+1)}}$

$={\frac {z^{20}-z^{10}+1}{z^{4}-z^{2}+1}}$

$=z^{16}+z^{14}-z^{10}-z^{8}-z^{6}+z^{2}+1$.

Construction from complex roots

It is also possible to construct a cyclotomic polynomial from the complex roots of 1:

$\Phi _{n}(z)=\prod _{k=1}^{\varphi (n)}(z-e^{{\frac {2\pi k}{n}}j})\;$

where $\phi (n)$ is Euler's totient function. For example,

$\Phi _{6}(z)=(z-e^{{\frac {\pi }{3}}j})(z-e^{{\frac {5\pi }{3}}j})=z^{2}-z+1.$

Some special cases

When p and q are odd primes,

$\Phi _{p}(z)={\frac {z^{p}-1}{z-1}}=\sum _{k=0}^{p-1}z^{k}$

$\Phi _{2p}(z)={\frac {z^{p}+1}{z+1}}=\sum _{k=0}^{p-1}(-z)^{k}$

$\Phi _{pq}(z)={\frac {(z^{pq}-1)(z-1)}{(z^{p}-1)(z^{q}-1)}}={\frac {\sum _{k=0}^{q-1}z^{pk}}{\sum _{k=0}^{q-1}z^{k}}}$

Galois Theory

The Galois group associated to the nth cyclotomic polynomial is $(\mathbb {Z} /n\mathbb {Z} )^{*}$, the group of cyclic units modulo n. Cyclotomic fields play an important part in algebraic number theory and can be used to show that certain constructions posited by ancient Greek geometers are impossible, such as trisecting the angle and constructing certain regular polygons.