Cyclotomic polynomials

In this post, we consider cyclotomic polynomials, which are a special class of polynomials with various connections to number theory, algebra, and even the constructability of regular polygons using ruler and compass. After deriving the basic properties of cyclotomic polynomials, we use them to give an elementary proof of the infinitude of primes $p\equiv 1 \pmod n$, as well as to determine which regular polygons are constructable. In a later post, we will also see Zsigmondy's theorem on the prime divisors of $a^n-b^n$ as an application of the properties of these polynomials. We assume mostly just basic properties of complex numbers, so the post is suitable for olympiad level.

The cyclotomic polynomials arise from a very simple equation: the equation $z^n=1$, whose complex roots, the $n$th roots of unity, are given by $1,e^{\frac{2\pi i}{n}},...,e^{\frac{2\pi i(n-1)}{n}}$, where $e^{ix}=\cos x +i\sin x$. The number $n$ will always be a positive integer. The roots form a regular $n$-gon in the complex plane. A root $\zeta$ of the equation $z^n=1$ is called a primitive $n$th root of unity if $\zeta^k\neq 1$ for $k<n$, or equivalently if the set $\{1,\zeta,...,\zeta^{n-1}\}$ contains all the roots of $z^n=1$. Then we define the $n$th cyclotomic polynomial as

\[\begin{eqnarray}\Phi_n(x):=\prod_{\zeta\in S_n}(x-\zeta),\end{eqnarray}\]

where $S_n$ is the set of primitive $n$th roots of unity. Clearly the primitive roots are $e^{\frac{2\pi i k}{n}},$ where $(k,n)=1$, so there are $\varphi(n)$ of them. Hence $\Phi_n(x)$ is a monic polynomial of degree $\varphi(n)$. If $\zeta$ is any $n$th root of unity, then $\zeta$ is in a unique $S_d$ where $d\leq n$. We have $d\mid n$ since if $n=kd+r$ with $0<r<d$, we would actually have $\zeta\in S_r$. This gives the important identity

\[\begin{eqnarray}x^n-1=\prod_{d\mid n}\Phi_d(x),\end{eqnarray}\]

since both sides are monic polynomials and the roots of the right-hand side are the elements of the sets $S_d$ for $d\mid n$ (there are no multiple roots as each root belongs to a unique $S_d$). This formula allows us for example to calculate cyclotomic polynomials explicitly. Obviously $\Phi_1(x)=x-1$, and then
\[\begin{eqnarray}\Phi_n(x)=\frac{x^n-1}{\prod'_{d\mid n} \Phi_d(x)},\end{eqnarray}\]

where $'$ denotes that the term $d=n$ is ignored. Hence each cyclotomic polynomial is determined by the previous ones. In particular, the following holds.