What's next in this sequence of polynomials?
  • x-1
  • x+1
  • x2+x+1
  • x2+1
  • x4+x3+x2+x+1

These are the first 5 cyclotomic polynomials. The nth cyclotomic polynomial is
where e1,e2,...,er are the primitive complex nth roots of unity.

It follows from the definition that the degree of cycn is phi(n), where phi is the Euler Phi function.

In the case of a prime number p we get
(because all the pth roots of unity are primitive except for 1).

The cyclotomic polynomials can be calculated recursively because of the formula
xn-1=product over all d|n of cycd(x)

This formula follows because the roots of xn-1 are exactly the nth roots of unity. By Lagrange's Theorem each nth root of unity is a primitive dth root of unity for some divisor d of n. On the other hand clearly any such primitive dth root of unity is an nth root of unity.

Let's do this for an example, n=6. The divisors of 6 are 1,2,3,6 so the formula tells us

We obtain from this that cyc6(x)=x2-x+1.

A couple more interesting properties of cycn(x)