Background (skip to definitions)
Euler proved a beautiful theorem about the complex numbers: \$e^{ix} = \cos(x) + i \sin(x)\$.
This makes de Moivre's theorem easy to prove:
$$ (e^{ix})^n = e^{i(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(\frac 4 3))\$ in polar coordinates. The first number, \$r\$, is the distance of the point from the origin; the second number, \$\theta\$, is the angle measured from the positive \$x\$-axis to the point, counter-clockwise. As a result, \$3 = r \cos \theta\$ and \$4 = r \sin \theta\$. Therefore, we can write \$3+4i\$ as \$r \cos \theta + r i \sin \theta = r(\cos \theta + i \sin \theta) = re^{i\theta}\$.
Let us solve the complex equation \$z^n = 1\$, where \$n\$ is a positive integer.
We let \$z = re^{i\theta}\$. Then, \$z^n = r^ne^{in\theta}\$. The distance of \$z^n\$ from the origin is \$r^n\$, and the angle is \$n\theta\$. However, we know that the distance of 1 from the origin is 1, and the angle is \$\theta\$. Therefore, \$r^n=1\$ and \$n\theta=\theta\$. 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\theta = 2kπ\$, giving us \$z=e^{2ikπ / n}\$.
We restate our discovery: the solutions to \$z^n=1\$ are \$z=e^{2ikπ / n}\$.
A polynomial can be expressed in terms of its roots. For example, the roots of \$x^2-3x+2\$ are 1 and 2, so \$x^{2}-3x+2 = (x-1)(x-2)\$. Similarly, from our discovery above:
$$z^n-1 = \prod^{n-1}_{k=0} (z-e^{2ik\pi / n})$$
However, that product certainly contained roots of other n. For example, take \$n=8\$. The roots of \$z^{4}=1\$ would also be included inside the roots of \$z^{8}=1\$, since \$z^{4}=1\$ implies \$z^{8} = (z^{4})^{2} = 1^{2} = 1\$. Take \$n=6\$ as an example. If \$z^{2}=1\$, then we would also have \$z^{6}=1\$. Likewise, if \$z^{3}=1\$, then \$z^{6}=1\$.
If we want to extract the roots unique to \$z^{n}=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 \$\frac k d\$-th root of \$z^{n / d}=1\$. Using the technique above to write the polynomial in terms of its roots, we obtain the polynomial:
$$\prod_{\substack{0 \le k < n \\ \gcd(k,n) = 1}} (z - e^{2ik\pi / n})$$
Note that this polynomial is done by removing the roots of \$z^{n / 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 \$z^{n / 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 \$z^{n}-1\$, the quotient must be a polynomial with integer coefficient, and the quotient is the polynomial above.
The roots of \$z^{n}=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)
Definition 1
The n-th cyclotomic polynomial, denoted \$\Phi_n(x)\$, is the unique polynomial with integer coefficients that divide \$x^{n}-1\$ but not \$x^{k}-1\$ for \$k < n\$.
Definition 2
The cyclotomic polynomials are a set of polynomials, one for each positive integer, such that:
$$x^n - 1 = \prod_{k \mid n} \Phi_k(x)$$
where \$k \mid n\$ means \$k\$ divides \$n\$.
Definition 3
The \$n\$-th cyclotomic polynomial is the polynomial \$x^{n}-1\$ divided by the LCM of the polynomials in the form \$x^{k}-1\$ where \$k\$ divides \$n\$ and \$k < n\$.
Examples
- \$Φ_{1}(x) = x - 1\$
- \$Φ_{2}(x) = x + 1\$
- \$Φ_{3}(x) = x^{2} + x + 1\$
- \$Φ_{30}(x) = x^{8} + x^{7} - x^{5} - x^{4} - x^{3} + x + 1\$
- \$Φ_{105}(x) = x^{48} + x^{47} + x^{46} - x^{43} - x^{42} - 2x^{41} - x^{40} - x^{39} + x^{36} + x^{35} + x^{34} + x^{33} + x^{32} + x^{31} - x^{28} - x^{26} - x^{24} - x^{22} - x^{20} + x^{17} + x^{16} + x^{15} + x^{14} + x^{13} + x^{12} - x^{9} - x^{8} - 2x^{7} - x^{6} - x^{5} + x^{2} + x + 1\$
Task
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).
Rules
You may return floating point/complex numbers as long as they round to the correct value.
Scoring
This is code-golf. Shortest answer in bytes wins.
. Thanks @H.PWiz for quite a bunch of bytes!
