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
cycn(x)=(x-e1)(x-e2)...(x-er)
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
cycp(x)=(xp-1)/(x-1)=xp-1+xp-2+...+x+1
(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
x6-1=cyc1(x)cyc2(x)cyc3(x)cyc6(x)
=(x-1)(x+1)(x2+x+1)cyc6(x)
=(x2-1)(x2+x+1)cyc6(x)
=(x4+x3-x+1)cyc6(x)
We obtain from this that cyc6(x)=x2-x+1.
A couple more interesting properties of cycn(x)