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}}}$