Background (skip to definitions)
Euler proved a beautiful theorem about the complex numbers: eix = cos(x) + i sin(x).
This makes de Moivre's theorem easy to prove:
(eix)n = ei(nx)
(cos(x) + i sin(x))n = cos(nx) + i sin(nx)
We can plot complex numbers using the two-dimensional Euclidean plane, with the horizontal axis representing the real part and the vertical axis representing the imaginary part. This way, (3,4) would correspond to the complex number 3+4i.
If you are familiar with polar coordinates, (3,4) would be (5,arctan(4/3)) in polar coordinates. The first number, r, is the distance of the point from the origin; the second number, θ, is the angle measured from the positive x-axis to the point, counter-clockwise. As a result, 3 = r cosθ and 4 = r sinθ. Therefore, we can write 3+4i as r cosθ + r i sinθ = r(cosθ + i sinθ) = reiθ.
Let us solve the complex equation zn = 1, where n is a positive integer.
We let z = reiθ. Then, zn = rneinθ. The distance of zn from the origin is rn, and the angle is nθ. However, we know that the distance of 1 from the origin is 1, and the angle is 0. Therefore, rn=1 and nθ=0. However, if you rotate by 2π more, you still end up at the same point, because 2π is just a full circle. Therefore, r=1 and nθ = 2kπ, giving us z=e2ikπ/n.
We restate our discovery: the solutions to zn=1 are z=e2ikπ/n.
A polynomial can be expressed in terms of its roots. For example, the roots of x2-3x+2 are 1 and 2, so x2-3x+2 = (x-1)(x-2). Similarly, from our discovery above:
However, that product certainly contained roots of other n. For example, take n=8. The roots of z4=1 would also be included inside the roots of z8=1, since z4=1 implies z8 = (z4)2 = 12 = 1. Take n=6 as an example. If z2=1, then we would also have z6=1. Likewise, if z3=1, then z6=1.
If we want to extract the roots unique to zn=1, we would need k and n to share no common divisor except 1. Or else, if they share a common divisor d where d>1, then z would be the (k/d)-th root of zn/d=1. Using the technique above to write the polynomial in terms of its roots, we obtain the polynomial:
Note that this polynomial is done by removing the roots of zn/d=1 with d being a divisor of n. We claim that the polynomial above has integer coefficients. Consider the LCM of the polynomials in the form of zn/d-1 where d>1 and d divides n. The roots of the LCM are exactly the roots we wish to remove. Since each component has integer coefficients, the LCM also has integer coefficients. Since the LCM divides zn-1, the quotient must be a polynomial with integer coefficient, and the quotient is the polynomial above.
The roots of zn=1 all have radius 1, so they form a circle. The polynomial represents the points of the circle unique to n, so in a sense the polynomials form a partition of the circle. Therefore, the polynomial above is the n-th cyclotomic polynomial. (cyclo- = circle; tom- = to cut)
The n-th cyclotomic polynomial, denoted , is the unique polynomial with integer coefficients that divide xn-1 but not xk-1 for k<n.
The cyclotomic polynomials are a set of polynomials, one for each positive integer, such that:
where k | n means k divides n.
The n-th cyclotomic polynomial is the polynomial xn-1 divided by the LCM of the polynomials in the form xk-1 where k divides n and k<n.
- Φ1(x) = x - 1
- Φ2(x) = x + 1
- Φ3(x) = x2 + x + 1
- Φ30(x) = x8 + x7 - x5 - x4 - x3 + x + 1
- Φ105(x) = x48 + x47 + x46 - x43 - x42 - 2x41 - x40 - x39 + x36 + x35 + x34 + x33 + x32 + x31 - x28 - x26 - x24 - x22 - x20 + x17 + x16 + x15 + x14 + x13 + x12 - x9 - x8 - 2x7 - x6 - x5 + x2 + x + 1
Given a positive integer
n, return the
n-th cyclotomic polynomial as defined above, in a reasonable format (i.e. e.g. list of coefficients is allowed).
You may return floating point/complex numbers as long as they round to the correct value.
This is code-golf. Shortest answer in bytes wins.