Sunday, July 27, 2014

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.

Proposition 1. (i) If $p$ is a prime, then
(ii) More generally, if $p$ is a prime and $k$ is a positive integer, then \[\begin{eqnarray}\Phi_{p^k}(x)=\frac{x^{p^{k}}-1}{x^{p^{k-1}}-1}=x^{p^{k-1}(p-1)}+...+x^{p^{k-1}}+1.\end{eqnarray}\]

Proof. Part (i) is evident. Part (ii) can be proved by induction. Indeed, the case $k=1$ has already been considered, and assuming that the claim holds for all $k<m$ we get
so the proof is complete. ■

The few first cyclotomic polynomials are $x-1,x+1,x^2+x+1,x^{2}+1,x^4+x^3+x^2+x+1,x^2-x+1$. This already gives a hint of two interesting properties of cyclotomic polynomials, namely that they have integer coefficients and are moreover irreducible in $\mathbb{Z}[x]$, the set of polynomials with integer coefficients (it would be tempting to also guess that the coefficients are always $\pm 1$, but that is by no means true in general; $n=105$ is the smallest counter example). The first one of these claims is quite immediate.

Proposition 2. The polynomials $\Phi_n(x)$ have integer coefficients.

Proof. We use induction on $n$. Assume that the statement is valid for all $n<m$. Since
\[\begin{eqnarray}\Phi_m(x)=\frac{x^m-1}{\prod'_{d\mid m}\Phi_d(x)},\end{eqnarray}\]
(where again $d=m$ is excluded) the polynomial $\Phi_m(x)$ is the quotient of two monic polynomials with integer coefficients, say $f(x)$ and $g(x)$. When we perform the long division for $f(x)$ and $g(x),$ clearly all the steps in the long division only involve polynomials with integer coefficients. We end up with $\Phi_n(x)$ in the end, so it has integral coefficients.■

Irreducibility of cyclotomic polynomials

Proving that the polynomial $\Phi_n(x)$ is always irreducible is not that easy, but when $n$ is prime, it follows from Eisenstein's criterion, which is easy to prove and well-known.

Lemma 3 (Eisenstein's criterion). Let $f(x)=a_nx^n+...+a_1x+a_0\in \mathbb{Z}[x]$ be a polynomial with integer coefficients, and suppose that there is a prime $p$ such that
(i) $p\mid a_k$ for $k<n$
(ii) $p\nmid a_n$
(iii) $p^2\nmid a_0$.
Then $f(x)$ is irreducible in $\mathbb{Z}[x].$

Proof. Assume $f(x)=g(x)h(x)$ with $g(x)=b_mx^m+...+b_0,h(x)=c_kx^k+...+c_0$ for some integers $b_i$ and $c_i$ with $m,k\geq 1$. Then $p\mid b_0c_0$, $p^2\nmid b_0c_0$, so without loss of generality $p\mid b_0, p\nmid c_0$. By comparing the coefficients, we see that $p\mid b_1c_0+b_0c_1$ so $p\mid b_1$, and $p\mid b_2c_0+b_1c_1+b_0c_2$ so $p\mid b_2$, and so on. Eventually, we have $p\mid b_m$, so also $p\mid a_n$, which is a contradiction. ■

Now we can show the case of prime values of $n$.

Theorem 4. When $p$ is a prime, $\Phi_p(x)$ is irreducible in $\mathbb{Z}[x]$.

Proof. Assume $\Phi_p(x)=f(x)g(x)$. Then $\frac{(x+1)^p-1}{x}=\Phi_{p}(x+1)=f(x+1)g(x+1)$. The coefficients of $\frac{(x+1)^p-1}{x}$ are $\binom{p}{k}$ for $1\leq k\leq p$. In particular, $p$ divides all the coefficients except the coefficient of the highest degree since $p$ is a prime, and also $p^2\nmid \binom{p}{1}.$ Now Eisenstein's criterion finishes the proof. ■

Next we present the general case; the following proof is due to Landau.

Theorem 5. For any $n$, $\Phi_n(x)$ is irreducible in $\mathbb{Z}[x]$.

Proof. Let $f(x)$ be an irreducible polynomial of degree $d$ with integer coefficients such that $f(x)\mid \Phi_n(x)$ and $f(\zeta)=0$, where $\zeta=e^{\frac{2\pi i}{n}}$. We will show that in fact $f(\zeta^k)=0$ whenever $(k,n)=1$, and after that $f(x)$ has all the elements of $S_n$ as its roots, so it is just a constant multiple of $\Phi_n(x)$.

Let us write $f(\zeta^m)=q_m(\zeta),$ where $q_m(x)\in \mathbb{Z}[x]$. We can assume that $\deg q_m<d$, since otherwise we can always use the identity $f(\zeta)=0$ to reduce its degree by one. With this restriction, $q_m$ becomes unique. We have $f(x^p)-f(x)^p=pg_p(x)$ for some $g_p(x)\in \mathbb{Z}[x]$. To see this, write $f(x)=a_dx^d+...+a_1x+a_0$ and multiply out $f(x)^p$; the result is $a_d^px^{dp}+...+a_1^px^p+a_0^p+ph_p(x)$, where $h_p(x)$ has integer coefficients since the binomial coefficients $\binom{p}{k},1\leq k<p,$ are divisible by $p$. The numbers $a_k-a_k^p$ are divisible by $p$ by Fermat's little theorem (which can be proved with a very similar argument). By the division algorithm, we may write $g_p(x)=f(x)G_p(x)+r_p(x)$ with $\deg r_p<d$ and $r_p$ and $G_p$ having integral coefficients.

Now $pr_p(\zeta)=q_p(\zeta)$ and $pr_p(x)-q_p(x)$ has degree smaller than $d$, so $pr_p(x)=q_p(x)$ for all $x$; otherwise there would exist an integral polynomial $f_1(x)$ of smaller degree than $f(x)$ (as small as possible) and having $\zeta$ as a root, which is impossible because then we could write $f(x)=f_1(x)s_1(x)+s_2(x)$ with $s_1(x),s_2(x)\in \mathbb{Z}[x]$ and $\deg s_2<\deg f_1$ and $s_2(\zeta)=0$, and $s_2(x)$ is not identically zero by the irreducibility of $f(x).$

Now notice that there are only finitely many distinct $q_i$ as $q_{i+n}(x)=q_i(x)$. Let $M$ be the largest absolute value of the coefficients of $q_i$. We now know that $p$ divides the coefficients of $q_k(x)$, where $k$ is such that $f(\zeta^p)=q_k(\zeta)$ and $1\leq k\leq n$, and hence for $p>M$ we must have $f(\zeta^p)=0.$ We can repeat the same argument for the polynomials $f(x^{\frac{m}{p}})$, where $p>M$ is prime and $m$ is divisible by $p$ (the only crucial thing is that $\zeta$ is a root for them and the roots are $n$th roots of unity) to see that $f(\zeta^m)=0$ when the prime divisors of $m$ are greater than $M$. The constant $M$ does not change with the polynomial, since $f((\zeta^{\frac{m}{p}})^k)=q_{k\frac{m}{p}}(\zeta)$, where the coefficients of $q_{k\frac{m}{p}}$ are bounded by the same $M$.

Now it suffices to show that for every $1\leq k<n$ with $(k,n)=1$ there exists an $m$ such that $m\equiv k \pmod n$ and $m$ has no prime divisor smaller than $M$. If $p_1,...,p_N$ are the primes below $M$ that do not divide $n$, by the Chinese remainder theorem we may choose $m$ so that
\[\begin{eqnarray}m&\equiv k \pmod n\\m&\equiv 1 \pmod{p_1}\\&...\\m &\equiv 1 \pmod{p_N}.\end{eqnarray}\]
This $m$ has no prime divisor below $M$, so $f(\zeta^k)=f(\zeta^m)=0$ and we are done ($f$ is a constant multiple of the cyclotomic polynomial). ■

A special case of Dirichlet's theorem

Next we use $\Phi_n(x)$ to show in an elementary way that there are infinitely many primes $p\equiv 1 \pmod n$. It is good to know that Dirichlet's theorem on the infinitude of primes $p\equiv a \pmod n$ with $(a,n)=1$ has no ''Euclid-style'' proof (a proof based on prime divisors of polynomials) unless $a^2\equiv 1\pmod n$, and in these cases there actually is such a proof. This is a theorem of Schur and Murty (Schur proved the positive statement in 1912 and Murty proved the negative one in 1988).

We start with the result telling that the existence of suitable polynomials implies the infinitude of primes of certain forms.

Theorem 6. Let $f(x)\in \mathbb{Z}[x]$ be a polynomial. Then the set of prime divisors of $f(x)$ (that is, the set of primes $q$ that divide some of these numbers) is infinite.

Proof. First assume that $f(0)=\pm 1$. We mimic Euclid's proof for the infinitude of primes. Suppose that $p_1,...,p_N$ are all the primes of the desired form, and let $k$ be large. Consider the number $f(kp_1...p_N)$. Since $k$ is large, this number has absolute value greater than $1$, so it is divisible by some $p_i$. However, it satisfies $f(kp_1...p_N)\equiv f(0)\equiv \pm 1 \pmod{p_1....p_N},$ so we have a contradiction. The general case follows by denoting $a=f(0)$ (we may assume $a\neq 0$) and considering the polynomial $g(x)=\frac{f(ax)}{a}$ which has integral coefficients and constant coefficient equal to $1$. ■

The theorem above implies for example the infinitude of primes $p\equiv 1 \pmod 4$ as all the prime divisors of $x^2+1$ except $2$ are of this form. We want to show that the prime divisors of $\Phi_n(x)$ are $\equiv 1 \pmod n$ with finitely many exceptions. We start with the case where $n$ is a prime power, and this time it is easy to generalize, unlike in the irreducibility proof.

Theorem 7. Let $p$ be a prime and $k$ a positive integer. Then the prime divisors $q$ of $\Phi_{p^k}(x)$ satisfy $q=p$ or $q\equiv 1 \pmod{p^k}.$

Proof. Let $q\mid \frac{x^{p^k}-1}{x^{p^{k-1}}-1}$ for some integer $x\neq 1$, and $q\nmid p$. Then $x^{p^k}\equiv 1 \pmod q$. Let $d=\text{ord}_p(x)$ ($d$ satisfies $x^d\equiv 1 \pmod p$ and is as small as possible). As in the primitive roots post, we have $d\mid p^k$ so $d=p^a$ for some $a\leq k$. If $a=k$, then $d\mid q-1$ implies $q\equiv 1 \pmod{p^k}$. If $a<k$, then the largest power of $q$ dividing $x^{p^k}-1$ is the same as the largest power of $q$ dividing $x^{p^a}-1$ (this is lifting the exponent lemma. Alternatively, one can just write $x^{p^k}-1=(x^{p^a}-1)g(x)$ and notice that $q\nmid g(x)$). In particular, $q$ does not divide $\frac{x^{p^k}-1}{x^{p^{k-1}}-1};$ a contradiction. ■

To prove the general case, we present a formula that allows to deduce the properties of $\Phi_{pn}(x)$ for a prime $p$ from those of $\Phi_n(x)$.

Proposition 8. Let $p$ be a prime. Then if $p\mid n$, we have
and otherwise we have

Proof. The primitive roots of unity of order $pn$ are $e^{\frac{2\pi i k}{np}}$ where $(k,pn)=1$. If $p\mid n$, the condition $(k,pn)=1$ means $(k,n)=1$, so every $x\in S_{pn}$ satisfies $x^p\in S_n$. The number of equations $x^p\in S_n$ is $\varphi(n)$, so they have $p\varphi(n)=\varphi(pn)$ roots in total. Therefore, the roots are precisely the elements of $S_{pn}.$ Now the polynomials $\Phi_{pn}(x)$ and $\Phi_n(x^p)$ are monic, have the same degree and the same roots, and the roots are not of higher order. This proves the first case. If $p$ does not divide $n$, we similarly see that for $x\in S_{pn}$ we have $x^p\in S_{n}$, and in addition $x\not \in S_n$. These equations with the additional condition have $(p-1)\varphi(n)$ roots, so the roots are precisely the elements of $S_{pn}$. Now the same argument as before finishes the proof. ■

Now we can prove the general claim.

Theorem 9. If $q$ is a prime and $q\mid \Phi_n(x)$, then $q\mid n$ or $q\equiv 1 \pmod n$. Consequently, there are infinitely many primes $q\equiv 1 \pmod n$.

Proof. Assume that $q\mid \Phi_n(x)$ and $q\nmid n$. Write $n=p_1^{\alpha_1}...p_k^{\alpha_k}$ where $p_i$ are distinct primes. Iterating the previous proposition, we get $\Phi_{p^k m}=\frac{\Phi_{m}(x^{p^k})}{\Phi_m(x^{p^{k-1}})}$ when $p\nmid m$. Therefore
\[\begin{eqnarray}q\mid \Phi_n(x)=\frac{\Phi_{\frac{n}{p_1^{\alpha_1}}}(x^{p_1^{\alpha_1}})}{\Phi_{\frac{n}{p_1^{\alpha_1}}}(x^{p_1^{\alpha_1-1}})}.\end{eqnarray}\]
This means that $q$ divides a value of $\Phi_{\frac{n}{p_1^{\alpha_1}}}$, so $q\equiv 1 \pmod{\frac{n}{p_1^{\alpha_1}}}$. Also $q\mid\Phi_{p_1^{\alpha_1}}(x^{\frac{n}{p_1^{\alpha_1}}})$ as by comparing roots one sees that $\frac{\Phi_m(x^{p^k})}{\Phi_m(x^{p^{k-1}})}\mid\Phi_{p^k}(x^m)$ if $p\nmid m$ (the first polynomial has roots $e^{\frac{2\pi i r}{p^k m}}$ where $ (r,pm)=1$, while the second has the roots $e^{\frac{2\pi i r}{p^km}}$ where $(r,p)=1$). Now $q$ also divides a value of $\Phi_{p_1^{\alpha_1}}$, so $n\equiv 1 \pmod{p_1^{\alpha_1}}$ and the claim follows. ■

Constructability of regular polygons

The cyclotomic polynomials can even be applied to prove the existence or impossibility of certain ruler and compass constructions. Such constructions were studied widely starting from the classical era until algebra was able to prove the impossibility of certain constructions. The question that can be solved with cyclotomic polynomials is '''which regular $n$-gons are constructible''? Constructable means that given a ruler (which can form a line between given two points) and a compass (which can draw a circle, given the center and the radius) and two points in the plane, it is possible to draw the figure in a finite number of steps (steps are constructions of lines and circles). The cases $n=3,4,5$ were known to be possible even before Euclid. These cases imply some others, as any angle can be bisected. Gauss managed to do the case $n=17$ and actually to solve the whole problem. Before starting with the proof, we need some algebraic concepts.

Definition. A complex number is called algebraic if it satisfies a polynomial equation with integer coefficients. If $\alpha$ is algebraic, its degree, $\text{deg}(\alpha)$, is the smallest degree of an integral polynomial $f$ whose root it is. Such a polynomial $f$ (if its coefficients do not have a common factor) is called the minimal polynomial of $\alpha$, denoted $\text{minpol}(\alpha)$.

Theorem 10. For any algebraic $\alpha$, $\text{minpol}(\alpha)$ is unique and irreducible. If $g(\alpha)=0$ and $g(x)\in \mathbb{Z}[x]$, then $\text{minpol}(\alpha)(x)\mid g(x)$.

Proof. If $f(x)$ and $g(x)$ were minimal polynomials, then the polynomial $af(x)-bg(x)$ would also have $\alpha$ as its root, but it would have a smaller degree if $a$ and $b$ are chosen suitably. Next assume that $f(x)$ is the minimal polynomial and $f(x)=g(x)h(x)$. Then $g(\alpha)=0$ or $h(\alpha)=0$, which is a contradiction. Finally, if $f(x)$ is the minimal polynomial and $g(x)=f(x)q(x)+r(x)$ with $\deg r<\deg f$, then $g(\alpha)=0$ implies $r(\alpha)=0$, so actually $r(x)=0$ for all $x$. ■

A couple of more things are needed for the existence direction of the theorem on $n$-gons.

Definition. A polynomial $f(x_1,...,x_k)$ (this is a finite linear combination of terms $x_1^{a_1}...x_k^{a_k}$) is symmetric if $f(x_1,...,x_k)=f(x_{\sigma(1)},...,x_{\sigma(k)})$ for any permutation $\sigma$ of $\{1,...,k\}$.

Definition. The elementary symmetric polynomials in $x_1,...,x_k$ are the polynomials $s_1=x_1+...+x_k,s_2=\sum_{i<j} x_ix_j,...,s_{k}=x_1...x_k$.

Theorem 11. Let $f(x_1,...,x_k)$ be symmetric, with its coefficients from a field $K$. Then $f(x_1,...,x_k)=P(s_1,...,s_k)$ for some polynomial $P$, whose coefficients are from $K$, where $s_1,...,s_k$ are the elementary symmetric polynomials.

Proof. We can express $f(x_1,...,x_k)$ as a linear combination of the polynomials $\sum_{sym}x_1^{a_1}...x_k^{a_k}$, where $\sum_{sym}$ means the sum over all permutations of $x_1,...,x_k$ (for example, $\sum_{sym}x_1^2x_2x_3=2(x_1^2x_2x_3+x_1x_2^2x_3+x_1x_2x_3^2)$ if $k=3$). Therefore, it suffices to consider these polynomials. The degree of such a polynomial is defined as $a_1+...+a_k$. Let $\sum_{sym}x_{i_1}^{b_1}...x_{i_r}^{b_r}$ be our homogeneous polynomial, where $b_1\geq b_2\geq...\geq b_r>0$ for all $i$. Assume that it is not of the desired form and that it is minimal in the lexicographic order (in this order one first compares the degree, then one compares $b_1$'s, then the $b_2$'s, and so forth). We may write
\[\begin{eqnarray}\sum_{sym}x_{i_1}^{b_1}...x_{i_r}^{b_r}=s_r \sum_{sym}x_{i_1}^{b_1-1}...x_{i_r}^{b_r-1}\end{eqnarray}+f(x_1,...,x_k),\]
and the the new expressions are smaller lexicographically, so they are of the desired form, and therefore the original is also. This is a contradiction. ■

Theorem 12. A regular $n$-gon can be constructed with ruler and compass if and only if $n=2^{a}p_1....p_k$ where $p_i$ are Fermat primes, that is primes of the form $2^{2^n}+1$.

Proof. We may assume that we are given the points $0=0+0i$ and $1=1+0i$ in the (complex) plane. At every step, we construct an at most quadratic equation (obtained by intersecting lines or circles) whose coefficients involve the coordinates known points, and use it to obtain more points. We say that a complex number $\alpha$ is constructable if we can attain the number $\alpha$ as a point. It is easy to see that the constructable numbers form a field $K$, that is they are closed under subtraction and division (division can be performed with similar triangles). The field K is also closed under square roots, as given any segment of length $|\alpha|$, we can construct $\sqrt{|\alpha|}$ as the geometric mean of $1$ and $|\alpha|$, and we can also bisect any angle. The order of each number in $K$ is a power of $2$ as new numbers are always obtained from quadratics using the old ones. We claim that if $n$ is not of the desired form, then $e^{\frac{2\pi i}{n}}$ is not constructable (if we cannot construct the regular $n$-gon that has this vertex, we cannot construct other regular $n$-gons either). Since $\Phi_n(x)$ was shown to be irreducible, $e^{\frac{2\pi i}{n}}$ has degree $n$ (as $\Phi_n$ is its minimal polynomial). This degree must be a power of two for the number to be constructable, but then every odd prime divisor of $n$ must be of the form $2^{\ell}+1$ (and $\ell$ is a power of two as otherwise the number is composite) and they must occur to power $1$.

Now we show that if the assumption is satisfied, the construction is possible. It suffices to construct the number $e^{\frac{2\pi i}{n}}$ since then we can also construct the other vertices of the $n$-gon by rotating the angle $\frac{2\pi}{n}.$ Since angles can always be bisected, it suffices to consider the case of an odd $n$. We may further assume that $n$ is a Fermat prime since if a regular $k$-gon and a regular $m$-gon can be constructed, where $k$ and $m$ are coprime, also a $km$-gon can be. This follows by writing $1=ak+bm$ for some integers $a$ and $b$ and then $e^{\frac{2\pi i}{km}} =e^{\frac{2\pi ia}{m}}e^{\frac{2\pi ib}{k}}$, which is a product of constructable numbers.

The harder part is showing that a regular $p$-gon is constructable if $p$ is a Fermat prime. We use the Lagrange resolvent to express a primitive $p$th root of unity in terms of nested square roots. Let $r$ be a primitive root $\pmod p$ (see this earlier post). Then if $\zeta=e^{\frac{2\pi i}{p}}$, the roots of $\Phi_p(x)$ are given by $\zeta,\zeta^r,...,\zeta^{r^{p-2}}$. Let $\eta=e^{\frac{2\pi i}{p-1}}$ (a number that can be constructed by bisecting angles). Let $L(\zeta,\eta^k)=\zeta+ \zeta^r\eta^k+\zeta^{r^2}\eta^{2k}+...+\zeta^{r^{p-2}}\eta^{(p-2)k}$ be the resolvent. Summing for $0\leq k\leq p-2$, we obtain
\[\begin{eqnarray} \sum_{k=0}^{p-2} L(\zeta,\eta^k)=(p-1)\zeta\end{eqnarray}\]
since $\zeta^{r^k}$ gets the coefficient $1+\eta^k+\eta^{2k}+...+\eta^{(p-2)k}=\frac{\eta^{k(p-1)}-1}{\eta^k-1}=0$. Now it suffices to show that the resolvents $ L(\zeta,\eta^k)$ are obtained by taking successive square roots. We compute $L(\zeta,1)=\sum_{m=0}^{p-2}\zeta^{r^m}=-1$. Next observe that $L(\zeta,\eta)=\eta^{k}L(\zeta^{r^k},\eta)$ so $L(\zeta,\eta)^{p-1}=L(\zeta^{r^k},\eta)^{p-1}$. This implies
\[\begin{eqnarray}L(\zeta,\eta)^{p-1}=\frac{1}{p-1}\sum_{k=0}^{p-2} L(\zeta^{r^k},\eta)^{p-1}.\end{eqnarray}\]
The right-hand side can be viewed as a symmetric polynomial in the variables $\zeta,\zeta^r,...,\zeta^{r^{p-2}}$, with coefficients being powers of $\eta$ times rational numbers. By the theorem on symmetric polynomials, this polynomial (or expression) is of the form $P_1(\eta)$ where $P_1(x)\in \mathbb{Q}[x]$, as the elementary symmetric polynomials in the variables $\zeta,\zeta^r,...,\zeta^{r^{p-2}}$ are just $0$ or $\pm 1$ by Vieta's formulas. Similarly, $L(\zeta,\eta^k)^{p-1}=P_k(\eta)$ for some rational polynomials $P_k$. Now $L(\zeta,\eta^k)=\gamma_k\sqrt[p-1]{P_k(\eta)}$, where $\gamma_k$ are certain roots of unity of order $p-1$ and $\sqrt[p-1]{x}$ is a fixed $p-1$st root function, say the one form which $\sqrt[p-1]{e^{ix}}=e^{\frac{ix}{p-1}}.$ We arrived at \[\begin{eqnarray} \sum_{k=0}^{p-2} \gamma_k\sqrt[p-1]{P_k(\eta)}=(p-1)\zeta.\end{eqnarray}\]
The left-hand side is a constructable number since $\eta$ and $\gamma_k$ can be constructed by bisecting angles, $P_k(\eta)$ is obtained from $\eta$ with elementary operations, and a root of order $p-1$ is just a number of successive square roots. Therefore $\zeta$ is constructable, and so the $p$-gon is too. ■