Cox_Galois_Chapter9.tex

%&LaTeX
\documentclass[11pt,a4paper]{article}
\usepackage[frenchb,english]{babel}
\usepackage[applemac]{inputenc}
\usepackage[OT1]{fontenc}
\usepackage[]{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{tikz}
%\input{8bitdefs}

% marges
\topmargin 10pt
\headsep 10pt
\headheight 10pt
\marginparwidth 30pt
\oddsidemargin 40pt
\evensidemargin 40pt
\footskip 30pt
\textheight 670pt
\textwidth 420pt

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}% intervalles d'entiers 
\def\dcro{\mbox{]\hspace{-.15em}]}}

\newcommand{\be} {\begin{enumerate}}
\newcommand{\ee} {\end{enumerate}}
\newcommand{\deb}{\begin{eqnarray*}}
\newcommand{\fin}{\end{eqnarray*}}
\newcommand{\ssi} {si et seulement si }
\newcommand{\D}{\mathrm{d}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\U}{\mathbb{U}}
\newcommand{\re}{\,\mathrm{Re}\,}
\newcommand{\im}{\,\mathrm{Im}\,}
\newcommand{\ord}{\mathrm{ord}}
\newcommand{\Gal}{\mathrm{Gal}}
\newcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\title{Solutions to David A.Cox  "Galois Theory''}
\author{Richard Ganaye}
\refstepcounter{section} \refstepcounter{section} \refstepcounter{section} \refstepcounter{section}
\refstepcounter{section}\refstepcounter{section}\refstepcounter{section}\refstepcounter{section}

\begin{document}


\section{Chapter 9 : CYCLOTOMIC EXTENSIONS}

\subsection{CYCLOTOMIC POLYNOMIALS}

\paragraph{Ex. 9.1.1}

{\it Prove that a congruence class $[i] \in \Z/n\Z$ has a multiplicative inverse if and only if $\mathrm{gcd}(i,n) = 1$. Conclude that $(\Z/n\Z)^*$ has order $\phi(n)$. Be sure you understand what happens when $n=1$.
}

\begin{proof}
If $[i]$ has a multiplicative inverse in the ring $\Z/n\Z$, then there exists $[j] \in \Z/n\Z$ such  that $[i][j] = [ij] = 1$, so $ij \equiv 1\ [n]$. Thus there exists $k\in \Z$ such that $ij - k n =1$. This B\'ezout's relation between $i$ and $n$ shows that $i\wedge n=1$.

Conversely, if $i\wedge n=1$, by  B\'ezout's Theorem, there exist integers $j,k$ such that $ij-kn=1$, so $[i] [j] = [1]$, and $[i]$ has a multiplicative inverse $\Z/n\Z$.

$$[i] \in (\Z/n\Z)^* \iff i\wedge n=1.$$

The mapping 
$$
\left\{
\begin{array}{ccc}
\{i \in \N\  \vert \ 0\leq i <n, i \wedge n = 1\} &  \to  &  (\Z/n\Z)^* \\
 i  &  \mapsto &   [i]
\end{array}
\right.
$$
obtained by restriction of the bijection $\gcro 0, n \gcro \to\Z/n\Z ,\  i \mapsto [i]$,  is well defined, and this is a bijection.

Therefore $$\vert (\Z/n\Z)^* \vert = \mathrm{Card} (\{i \in \N\  \vert \ 0\leq i <n, i \wedge n = 1\} = \phi(n).$$

If $n = 1$, the ring $\Z/1\Z$ is the trivial ring $\{[0]\}$, where $[0]=[1]$, so the multiplicative group $(\Z/1\Z)^* = \{[1]\}$ has one element, and the set of integers $i$ such that $0 \leq i < 1=n$ is reduced to $\{0\}$, which satisfies $0\wedge 1 = 1$, so $ \phi(1)=1$.
\end{proof}

\paragraph{Ex. 9.1.2}

{\it Assume that $\gcd(n,m) =1$. By Lemma A.5.2, we have a ring isomorphism $\alpha : \Z/nm\Z \simeq \Z/n\Z \times \Z/m\Z$ that sends $[a]_{nm}$ to $([a_n],[a]_m)$. Prove that $\alpha$ induces a group isomorphism $(Z/nm\Z)^* \simeq (\Z/nZ)^* \times (\Z/m\Z)^*$.
}

\begin{proof}
Let $A,B$ are commutative rings (with unity). Then $$(A\times B)^* = A^*\times B^*.$$

Indeed, let $(a,b)\in A\times B$.

\begin{align*}
(a,b) \in (A\times B)^* &\iff \exists (c,d) \in A\times B, \ (a,b)(c,d) = (1,1)\\
 &\iff \exists c \in A, \exists d \in B, \ ac=1,bd=1\\
  &\iff a\in A^*, b\in B^* \\
  &\iff (a,b)\in A^*\times B^*.
 \end{align*}
Moreover, if $\varphi : A\to B$ is a ring isomorphism, then for all $a \in A^* \Rightarrow \varphi(a) \in A^*$, since $ab = 1_A \Rightarrow \varphi(a) \varphi(b) = \varphi(1_A) = 1_B$. So we can define
$\psi : A^* \to B^*$ by restriction with $a\mapsto \psi(a) = \varphi(a)$.

$\psi$ is a group homomorphism: if $u,v \in A^*, \psi(uv) = \varphi(uv) = \varphi(u)\varphi(v) = \psi(u)\psi(v)$, and $\psi$ is bijective:

$\bullet\ \varphi$ is injective, so its restriction $\psi$ if also injective.

$\bullet$ If $b\in B^*$, then there exists $d \in B$ such that $bd=1$. If we write $a=\varphi^{-1}(b), c=\varphi^{-1}(d)$, then $b=\varphi(a), d=\varphi(c), 1 = bd = \varphi(ac)$, so $ac = 1, a \in A^*$, thus $b=\psi(a)$, so $\psi$ is surjective.
$$A\simeq B \Rightarrow A^* \simeq B^*.$$
If we apply these two results to the rings $\Z/n\Z, \Z/m\Z$, we obtain
$$(\Z/nm\Z)^* \simeq (\Z/n\Z \times \\Z/m\Z)^* = (\Z/nZ)^* \times (\Z/m\Z)^*.$$
\end{proof}

\paragraph{Ex. 9.1.3}

{\it Let $\zeta_n = e^{2\pi i/n} \in \C$. Prove that $\zeta_n^i$ for $0\leq i <n$ and $\gcd(i,n) = 1$ are the primitive $n$th roots of unity in $\C$.
}

\begin{proof}
Let $\U_n$ be the group of $n$-th roots of unity in $\C$. Then $\U_n = \langle \zeta_n \rangle$, where $\zeta_n = e^{2i\pi/n}$. Write $o(x)$ the order of an element $x\in G$. Then $o(x)= \vert \langle x \rangle \vert$.

Recall that if $d>0$, $o(x)= d \iff (\forall k \in \Z,\  x^k = e \iff d \mid k)$.

For all $i \in \Z$,
$$o(\zeta_n^i)=\frac{n}{n\wedge i}.$$
Indeed, for all $k\in\Z$,
$$(\zeta_n ^i)^k = 1 \iff \zeta_n^{ik} = 1 \iff n \mid ik \iff \frac{n}{n\wedge i} \mid \frac{i}{n\wedge i} k \iff  \frac{n}{n\wedge i} \mid k$$
(since $\frac{n}{n\wedge i} \wedge \frac{i}{n\wedge i} = 1$).
So $o(\zeta_n^i)=\frac{n}{n\wedge i}$.

By definition, $\zeta$ is a primitive $n$th root of unity if and only if $\zeta$ is a generator of $\U_n$, if and only if $o(\zeta)= n$, so

$$\U_n = \langle \zeta_n^i \rangle \iff o(\zeta_n^i)= n \iff \frac{n}{n\wedge i} = n \iff n \wedge i = 1.$$
\end{proof}

\paragraph{Ex. 9.1.4}

{\it Let $R$ be an integral domain, and let $f,g\in R[x]$, where $f\ne 0$. If $K$ is the field of fractions of $R$, then we can divide $g$ by $f$ in $K[x]$ using the division algorithm of Theorem A.1.14. This gives $g = qf+r$, though $q,r \in K[x]$ need not lie in $R[x]$.
\be
\item[(a)] Show that dividing $x^2$ by $2x+1$ in $\Q[x]$ gives $x^2 = q\cdot (2x+1) + r$, where $q,r \in \Q[x]$ are not in $\Z[x]$, even though $x^2$ and $2x+1$ lie in $\Z[x]$.
\item[(b)] Show that if $f$ is monic, then the division algorithm gives $g=qf+r$, where $q,r \in R[x]$. Hence the division algorithm works over $R$ provides we divide by monic polynomials. 
\ee
}

\begin{proof}
\begin{enumerate}
\item[(a)]
$x^2 = (\frac{1}{2}x - \frac{1}{4})(2x+1)+\frac{1}{4}$.
The quotient $q(x) = \frac{1}{2}x - \frac{1}{4}$ is not in $\Z[x]$.

\item[(b)]
Let $f = x^m + b_{m-1}x^{m-1}+ \cdots+b_0$ be a fixed monic polynomial in  $R[x]$.

We show by induction on the degree $n$ the proposition

$P(n) : \forall g \in R[x], \deg(g) = n \Rightarrow \exists (q,r) \in R^2, \ g = qf+r,\  \deg(r) < \deg(f)$

(with the convention $\deg(0) = -\infty$).

We suppose that $P(k)$ is true for all $k<n$, and we prove $P(n)$. Let $g$ be any polynomial in $R[x]$.

$\bullet$ If $\deg(g) < m = \deg(f)$, then the pair $(q,r) = (0,g)$ is an answer.

$\bullet$ Suppose that $\deg(g) \geq m$.  Write $g = a_n x^n+ a_{n-1}x^{n-1}+ \cdots +a_0$, with $\deg(g) = n \geq m$ and $a_i \in R, i=0,\ldots,n$.

The polynomial $g_1 = g - a_n x^{n-m} f \in R[x]$ satisfies $\deg(g_1) < n$. We can then apply to it the induction hypothesis:

$g_1 =  q_1 f+r, q_1 \in R[x],\ r \in R[x],\ \deg(r) < \deg(f)$.

Then $g = (a_n x^{n-m} + q_1) f+ r$.

If we write $q = a_n x^{n-m} + q_1$, then $q \in \mathbb{R}[x]$ and $g = fq+r,\ (q,r) \in\mathbb{R}[x]^2, \deg(r) < \deg(f)$. The pair $(q,r)$ is an answer, and the induction is done.

In particular, if $g,f \in \mathbb{Z}[x]$ , and $g = f q$, the unicity of the Euclidean division in $\mathbb{Q}[x]$ and the preceding result shows that $q \in \mathbb{Z}[x]$.

\end{enumerate}
\end{proof}

\paragraph{Ex. 9.1.5}

{\it Verify the formula for $\Phi_{105}(x)$ given in Example 9.1.7.
}

\begin{proof}
The factors of $105 = 3\times5\times7$ are $105,35,21,15,7,5,3,1$, thus
$$x^{105} - 1 = \Phi_{105}\,\Phi_{35}\,\Phi_{21}\,\Phi_{15}\, \Phi_7\, \Phi_5\,\Phi_3\,\Phi_1.$$
As $x^{35}-1 = \Phi_{35}\, \Phi_7\, \Phi_5\, \Phi_1$, we obtain
$$x^{105}-1 = (x^{35}-1)\Phi_{105}\, \Phi_{21}\, \Phi_{15}\, \Phi_3,$$
that is
$$x^{70} + x^{35}+1 = \Phi_{105}\,\Phi_{21}\, \Phi_{15}\, \Phi_3.$$

Moreover $x^{21} - 1 = \Phi_{21}\,  \Phi_7\, \Phi_3\, \Phi_1$, so
\begin{align*}
\Phi_{21} &= (x^{21}-1)\, \frac{x-1}{x^7-1}\, \frac{x-1}{x^3-1}\, \frac{1}{x-1}\\
&= \frac{x^{21}-1}{(x^7-1)(x^2+x+1)}\\
&=\frac{x^{14} +x^7+1}{x^2+x+1}\\
&=x^{12} - x^{11} + x^9 -x^8 +x^6 -x^4 +x^3 -x+1.
\end{align*}

Similarly $x^{15}-1 = \Phi_{15}\,  \Phi_5\, \Phi_3\, \Phi_1$, so
\begin{align*}
\Phi_{15} &= \frac{x^{15}-1}{(x^5-1)(x^2+x+1)}\\
&=\frac{x^{10} +x^5+1}{x^2+x+1}\\
&=x^8 -x^7+x^5 -x^4+x^3 -x+1.
\end{align*}
Therefore
\begin{align*}
\Phi_{105} =& \frac{x^{70} + x^{35} + 1}{\Phi_{21} \Phi_{15} \Phi_3} \\
=& \frac{x^{70} + x^{35} + 1}{x^{22} - x^{21} + x^{19} - x^{18} + x^{17} + x^{12} - x^{11} + x^{10} + x^{5} - x^{4} + x^{3} - x + 1}\\
=&\quad x^{48} + x^{47} + x^{46} - x^{43} - x^{42} - 2 \, x^{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} \\
&- 2 \, x^{7} - x^{6} - x^{5} + x^{2} + x + 1
\end{align*}
\end{proof}

\paragraph{Ex. 9.1.6}

{\it This exercise is concerned with the proof of Lemma 9.1.8.
\be
\item[(a)] Let $f\in \Z[x_1,\ldots,x_n]$ be symmetric. Prove that $f$ is a polynomial in $\sigma_1,\ldots,\sigma_n$ with integer coefficients.
\item[(b)] Let $p$ be prime and let $h \in \F_p[x_1,\ldots,x_n]$. Prove that $h(x_1,\ldots,x_n)^p = h(x_1^p,\ldots,x_n^p)$.
\ee
}

\begin{proof}
\begin{enumerate}
\item[(a)]
The algorithm in the proof of Theorem 2.2.2 consists to replace the symmetric polynomial $f$, here with coefficients in $\Z$,  by $f_1 = f -c g, f_2 = f -c g -c_1g_1,\cdots$, until we obtain 0. The coefficient $c$ is the leading coefficient of $f$, so it is an integer, and $g= \sigma_1^{a_1-a_2}\cdots \sigma_{n-1}^{a_{n-1}-a_n}\sigma_n^{a_n} \in \Z[\sigma_1,\ldots,\sigma_n]$, so  $f_1 \in \Z[x_1,\ldots,x_n]$. The same reasoning applied to $f_1$ and to the following terms shows that $c_i \in \Z$ for all $i$. Therefore $$f  = cg+c_1g_1+\cdots+c_{m-1} g_{m-1}\in \Z[\sigma_1,\cdots,\sigma_n].$$
In particular, the symmetric polynomial $\sigma_i(x_1^p,\cdots,x_r^p) - \sigma_i(x_1,\cdots,x_r)^p$ is a polynomial in $\sigma_1,\ldots,\sigma_r$ with integer coefficients:
$$\sigma_i(x_1^p,\cdots,x_r^p) - \sigma_i(x_1,\cdots,x_r)^p = S(\sigma_1,\cdots,\sigma_r) \in \Z[\sigma_1,\cdots,\sigma_r].$$

\item[(b)]

Let $h \in \F_p[x_1,\ldots,x_n]$. Write $$h = \sum_{(i_1,\ldots,i_n) \in A} a_{i_1,\ldots,i_n} x_1^{i_1}\cdots x_n^{i_n},$$
where $A\subset \N^n$ is finite, and the coefficients $a_{i_1,\ldots,i_n} \in \F_p$.
As the characteristic of the field $\F_p(x_1,\cdots,x_r)$ is $p$, using the Little Fermat's Theorem: $a^p= a$ for all $a\in \F_p$,
\begin{align*}
f(x_1,\ldots,x_n)^p &= \left( \sum_{(i_1,\ldots,i_n) \in A} a_{i_1,\ldots,i_n} x_1^{i_1}\cdots x_n^{i_n} \right)^p\\
&=\sum_{(i_1,\ldots,i_n) \in A} a_{i_1,\ldots,i_n}^p x_1^{pi_1}\cdots x_n^{pi_n}\\
&=\sum_{(i_1,\ldots,i_n) \in A} a_{i_1,\ldots,i_n} x_1^{pi_1}\cdots x_n^{pi_n}\\
&=f(x_1^p,\ldots,x_n^p)
\end{align*}
In particular, write $\overline{\sigma}_i$ the projection of $\sigma_i$ in $\F_p[x_1,\cdots,x_r]$, and $\overline{S}$ the projection of $S$.
As the characteristic of the field $\F_p(x_1,\cdots,x_r)$ is $p$,

\begin{align*}
\overline{\sigma}_i(x_1,\cdots,x_r)^p &=  \left(\sum_{1\leq j_1 < j_2<\cdots<j_i\leq r} x_{j_1}\cdots x_{j_i}\right)^p\\
&=  \sum_{1\leq j_1 < j_2<\cdots<j_i\leq r} x_{j_1}^p\cdots x_{j_i}^p\\
&=\overline{\sigma}_i(x_1^p,\cdots,x_r^p)
\end{align*}
Hence $\overline{S}(\overline{\sigma}_1, \ldots, \overline{\sigma}_r) = \overline{\sigma}_i(x_1^p,\cdots,x_r^p) - \overline{\sigma}_i^p =  0$. Since $\overline{\sigma}_1, \ldots, \overline{\sigma}_r$ are algebraically independant over $\F_p$ (see Ex. 2.2.5),  $\overline{S} = 0$, so $S \equiv 0 \pmod p$.
Therefore $p$ divides all the coefficients of $S$.
\end{enumerate}
\end{proof}

\paragraph{Ex. 9.1.7}

{\it This exercise is concerned with the proof of Theorem 9.1.9.
\be
\item[(a)] Let $\zeta$ be a primitive $n$th root of unity, and let $i$ be relatively prime to $n$. Prove that $\zeta^i$ is a primitive $n$th root of unity and that every primitive $n$th root of unity is of this form.
\item[(b)] Let $\gamma_1,\ldots,\gamma_r$ be distinct primitive $n$th roots of unity and let $i$ be relatively prime to $n$. Prove that $\gamma_1^i,\ldots,\gamma_r^i$ are distinct.
\ee
}

\begin{proof}
Let $\zeta$ be a primitive $n$th root of unity, so $o(\zeta) = n$ (where we write $o(x)$ the order of an element $x$ in a group $G$).
We have proved in Exercise 3 that for all $i\in \Z$,
$$o(\zeta^i) = \frac{n}{n\wedge i}$$

In particular, if $i$ and $n$ are relatively prime ($n \wedge i = 1$), then $o(\zeta^i) = n$, so $\zeta^i$ is a primitive $n$th root of unity.

If $\xi$ is any primitive $n$th root of unity, as $\zeta$ is a generator of $\U_n$, $\xi= \zeta^i, 0 \leq i <n$. As $\zeta^i$ is a primitive $n$th root of unity, $o(\zeta^i)=n = \frac{n}{n\wedge i}$, so  $n\wedge i=1$. 
\item[(b)]
Let $i \in \Z$ relatively prime to $n$. Consider
$$
\varphi :
\left\{
\begin{array}{ccc}
   \U_n&  \to &\U_n   \\
    \lambda& \mapsto   &     \lambda^i
\end{array}
\right.
$$
$\varphi$ is a group homomorphism.

If $\lambda \in \ker(\varphi)$, then $\lambda = \zeta^k,\  k \in \Z$, and $1 = \lambda^i = \zeta^{ki}$, thus $n\mid ki$. Since $n \wedge i =1$, $n\mid k$, hence $\lambda = \zeta^k = 1$, so $ \ker(\varphi) = \{1\}$.

The group homomorphism $\varphi$ is injective, so the images of the distinct $\gamma_1,\cdots,\gamma_r \in \U_n$ are distinct.

Conclusion:  if $i\wedge n = 1$, $\zeta \mapsto \zeta^i$ is a bijection from the set of primitive $n$th roots of unity on itself.

\end{proof}

\paragraph{Ex. 9.1.8}

{\it This exercise will present an alternate proof of (9.8) that doesn't use symmetric polynomials.  \begin{center}
(9.8) \qquad If $\zeta$ is a root of f, then so is $\zeta^p$.
\end{center}
where $f$ is an irreducible factor of $\Phi_n$, and $p$ a prime number such that $p\nmid n$.

Assume that $\zeta$ is a root of $f$ such that $f(\zeta^p) \ne 0$.
As in the text, $q(x) \in \Z[x]$ maps to the polynomial $\overline{q}(x) \in \F_p[x]$. Let $g(x)$ be as in (9.7), i.e. $\Phi_n(x) = f(x) g(x)$.
\be
\item[(a)] Prove that $\zeta$ is a root of $g(x^p)$, and conclude that $f(x) \mid g(x^p)$.
\item[(b)] Use Gauss's Lemma to explain why $f(x)$ divides $g(x^p)$ in $\Z[x]$, and conclude that $\overline{f}(x)$ divides $\overline{g}(x^p)$ in $\F_p[x]$.
\item[(c)] Use Exercise 7 to prove that $\overline{g}(x)^p = \overline{g}(x^p)$, and conclude that $\overline{f}(x)$ divides $\overline{g}(x)^p$.
\item[(d)] Now let $h(x) \in \F_p[x]$ be an irreducible factor of $\overline{f}(x)$. Show that $h(x)$ divides $\overline{g}(x)$, so that $h(x)^2$ divides $\overline{f}(x) \overline{g}(x)$.
\item[(e)] Conclude that $h(x)^2$ divides $x^n-1 \in \F_p[x]$.
\item[(f)] Use separability to obtain a contradiction.
\ee

}

\begin{proof}
 As in the proof of Theorem 9.1.9, the Gauss's Lemma in the form of Corollary 4.2.1 allows us to assume that there exists a polynomial $f(x)\in \Z[x]$ of $\Phi_n(x)$ such that
 $\Phi_n(x) = f(x) g(x),\  f(x),g(x) \in \Z[x]$, where $f$ is monic and irreducible over $\Q$. Let $p$ be a prime number such that $p\nmid n$.

Reasoning by contradiction, we suppose that $\zeta$ is a root of $f$ such that $f(\zeta^p)\neq 0$.
\begin{enumerate}
\item[(a)] As $\zeta$ is the root of $f$, where $f$ divides $\Phi_n$, $\zeta$ is a $n$th primitive root of unity. Since $p\nmid n, p\wedge n=1$, hence $\zeta^p$ is also a $n$th primitive root of unity by Exercise 7(a), therefore $0 = \Phi(\zeta^p) = f(\zeta^p) g(\zeta^p)$. As $f(\zeta^p) \neq 0$, $g(\zeta^p)=0$, so
\begin{center}
$\zeta$ is a root of $g(x^p)$.
\end{center}
As $f$ is irreducible, $f$ is the minimal polynomial of $\zeta$ over $\Q$, and $\zeta$ is a root of $g(x^p) \in \Q[x]$, hence
$$f(x) \mid g(x^p).$$

\item[(b)]
As $f$ is monic, the refined division algorithm of Exercise 4 show that the quotient $q(x)$ of $g(x^p)$ by $f(x)$ lies in $\Z[x]$, so $f(x)$ divides $g(x^p)$ in $\Z[x]$.

The projection homomorphism on $\F_p[x]$  gives $\overline{g}(x^p) = \overline{f}(x) \overline{q}(x)$, thus $\overline{f}(x)$ divides $\overline{g}(x^p)$ in $\F_p[x]$.

\item[(c)]

As the characteristic of $\F_p(x)$ is $p$, writing $\overline{g}(x) = \sum\limits_{i=0}^r a_i x^i \in \F_p[x]$, then (as in Exercise 7)

$$\overline{g}(x)^p =\left( \sum\limits_{i=0}^r a_i x^i\right)^p = \sum\limits_{i=0}^r a_i^p  x^{ip} = \sum\limits_{i=0}^r a_i  x^{ip} = \overline{g}(x^p).$$


Therefore $\overline{f}(x)$ divides $\overline{g}(x)^p$ in $\F_p[x]$.

\item[(d)] Let $h(x)  \in \F_p[x]$ an irreducible factor of $\overline{f}(x)$. Then $h(x) \mid \overline{g}(x)^p$. Since $h$ is irreducible (hence prime) in $\F_p[x]$, then  $h \mid \overline{g}$.

$h(x) \mid \overline{f}(x), h(x) \mid \overline{g}(x)$, so $h(x)^2 \mid \overline{f}(x)\overline{g}(x)$. 

\item[(e)] 
Therefore $h^2 \mid\overline{\Phi}_n$, and $\overline{\Phi}_n \mid x^n-1$, thus $h^2 \mid x^n-1\in F_p[x]$.

\item[(f)] As $\deg(h)>1$, every root of $h$ in the splitting root of $x^n-1\in \F_p[x]$ is not a simple root, thus $x^n-1$ would not be separable.

But $n$ is relatively prime to $p$, so $(x^n-1)' = nx^{n-1}$ is relatively prime to $x^n-1$, and so $x^n-1 \in \F_p[x]$ is separable: this is a contradiction, therefore.


$$f(\zeta) = 0 \Rightarrow f(\zeta^p)=0.$$

We conclude that $\Phi_n$ is irreducible as in the conclusion of the proof of Theorem 9.1.9.
\end{enumerate}
\end{proof}

\paragraph{Ex. 9.1.9}

{\it In proving Fermat's Little Theorem $a^p\equiv a \pmod p$, recall from the proof of Lemma 9.1.2 that we first proved $a^{p-1} \equiv 1 \pmod p$ when $a$ is relatively prime to $p$. For general $n>1$, Euler showed that $a^{\phi(n)} \equiv 1 \pmod n$ when $a$ is relatively prime to $n$. Prove this. What basic fact from group theory do you use?
}

\begin{proof}
If $a \wedge n = 1$, $[a] \in (\Z/n\Z)^*$.
By Lagrange Theorem, the order of $[a]$ divides the order of the group $(\Z/n\Z)^*$, therefore the order of $a$ divides $ \phi(n) = \vert (\Z/n\Z)^* \vert$, and so $[a]^{\phi(n)} = [1]$.

$$a \wedge n = 1 \Rightarrow a^{\phi(n)} \equiv 1 \ \pmod n.$$
\end{proof}

\paragraph{Ex. 9.1.10}

{\it Prove that a cyclic group of order $n$ has $\phi(n)$ generators.
}

\begin{proof}
More generally, we prove that a cyclic group $G$ of order $n$ has $\phi(d)$ elements of order $d$ if $d \mid n$ (0 otherwise !).

Let $\zeta$ a generator of $G$: $G = \langle \zeta \rangle$.

Every element $\alpha \in G$ is of the form $\zeta^k, 0 \leq k <n$. Recall (see Exercise 3), that 
$$o(\zeta^k) = \frac{n}{n\wedge k}.$$
If $d \nmid n$, there is no element of order $d$ by Lagrange's Theorem, and if $d \mid n$,
\begin{align*}
o(\zeta^k)  = d &\iff  \frac{n}{n\wedge k} = d\\
&\iff \frac{n}{d} = n \wedge k\\
&\iff\exists \lambda \in \Z,\  k = \lambda \frac{n}{d}, \ 0 \leq \lambda < d,\ \lambda \wedge d = 1.
\end{align*}

Indeed, if $\delta = \frac{n}{d} = n \wedge k$, then there exists $\lambda, \mu$, with $\lambda \wedge \mu = 1$, such that
$$
\left\{
\begin{array}{ccc}
 n &  = & \mu \delta,   \\
 k &   = & \lambda \delta.     
\end{array}
\right.
$$

$\mu = n/\delta = d$, so $\lambda \wedge d = 1$. As $0\leq k < n$, $0 \leq \lambda < n/\delta = d$.

Conversely, if $ k = \lambda \frac{n}{d}, \ \lambda \wedge d = 1$, then $$n\wedge k = d\frac{n}{d} \wedge\lambda \frac{n}{d} =  (d \wedge \lambda) \frac{n}{d}=  \frac{n}{d}.$$

The elements of order $d$ in $G$ are thus the elements $\zeta^k$, where $$k = \lambda \frac{n}{d}, \ 0 \leq \lambda < d,\ \lambda \wedge d = 1.$$

The mapping  $\varphi : \{\lambda \in \Z\ \vert \  0\leq \lambda <d, \lambda \wedge d = 1\} \to \{\alpha \in G \ \vert \ o(\alpha)= d\}$ 
defined by $\varphi(\lambda) = \zeta^{\lambda \frac{n}{d}}$ is so a bijection. 

Hence there exist exactly $\phi(d)$ elements of order $d$ in $G$, for every factor $d$ of $n = \vert G \vert$. In particular, there exist $\phi(n)$ elements of order $n = |G|$ in $G$, hence $\phi(n)$ generators in a cyclic group $G$ of order $n$.
\end{proof}

\paragraph{Ex. 9.1.11}

{\it Prove that $n = \sum_{d\mid n} \phi(d)$.
}

\begin{proof}
Let $G$ a fixed cyclic group of order $n$, by example $G =\U_n$. If $A_d$ is the set of elements of order $d$ in $G$, then  $G$ is the disjoint union of the $A_n$, so $\vert G  \vert = \sum_{d=0}^n \vert A_d \vert$.

By the proof of Exercise 10, $\vert A_d \vert = \phi(d)$ if $d\mid n$, and $\vert A_d \vert = 0$ if $d\nmid n$,  so
$$n = \sum_{d\mid n } \phi(d).$$
Note: as an alternative proof, we can take the degrees in the formula  $x^n-1 = \prod_{d\mid n} \Phi_d(n)$.
\end{proof}

\paragraph{Ex. 9.1.12}

{\it Here are some further properties of cyclotomic polynomials.
\be
\item[(a)] Given $n$, let $m =\prod_{d\mid n} p$. Prove that $\Phi_n(x) = \Phi_m(x^{n/m})$. This shows that we can reduce computing $\Phi_n(x)$ to the case when $n$ is squarefree.
\item[(b)] Let $n>1$ be an odd integer. Prove that $\Phi_{2n}(x) = \Phi_n(-x)$.
\item[(c)] Let $p$ be a prime not dividing an integer $n>1$. Prove that $\Phi_{pn}(x) = \Phi_n(x^p)/\Phi_n(x)$.
\ee
}



{\bf Lemma.} {\it  Let $f(x),g(x) \in \C[x]$ be two monic  polynomials in $\mathbb{Q}[x]$, of same degree $d$, and  $f$ separable.

If every  root of $f$ in $\mathbb{C}$ is a root of $g$, then $f=g$.}



{\it Proof of the Lemma.} 
As $f(x)$ is monic separable of degree $d$, the decomposition in irreducible factors of $f(x)$ in $\mathbb{C}[x]$ is

$$ f(x) = \prod_{\alpha \in S} (x-\alpha)$$  

The hypothesis implies that for all $\alpha \in S$, $x-\alpha \mid g(x)$, hence $f(x) \mid g(x)$. As $\deg(f) = \deg(g)$, and as $f,g$ are monic, then $f=g$.
\qed

\begin{proof}
\begin{enumerate}

\item[(a)]
$n = p_1^{\nu_1} p_2^{\nu_2}\cdots p_r^{\nu_r}$. Write $m = p_1\cdots p_r$.  Then

$\deg(\Phi_n(x)) = \phi(n) = p_1^{\nu_1-1} p_2^{\nu_2-1}\cdots p_r^{\nu_r-1}(p_1-1)(p_2-1)\cdots (p_r-1)$.

$\deg (\Phi_m(x))) = \phi(p_1 p_2\cdots p_n) = (p_1-1)(p_2-1)\cdots(p_r-1)$, therefore

$\deg (\Phi_m(x^{n/m})) = p_1^{\nu_1-1} p_2^{\nu_2-1}\cdots p_r^{\nu_r-1}(p_1-1)(p_2-1)\cdots (p_r-1) = \deg(\Phi_n(x))$.

Moreover these polynomials are monic and $\Phi_n$ is separable. It remains to show that every root $\zeta$ of $\Phi_n(x)$ is a root of $\Phi_m(x^{n/m})$.

Such a root  $\zeta$ has order $n = p_1^{\nu_1} p_2^{\nu_2}\cdots p_r^{\nu_r}$ in the group $\mathbb{C}^*$.

Write $\xi = \zeta^{n/m} = \zeta^{p_1^{\nu_1-1} p_2^{\nu_2-1}\cdots p_r^{\nu_r-1}}$.

Then the order of $\xi$ is $m = p_1p_2\cdots p_r$. Indeed,  for all $k \in \mathbb{Z}$,

$\xi^k=1 \iff \zeta ^{k p_1^{\nu_1-1} p_2^{\nu_2-1}\cdots p_r^{\nu_r-1}} = 1 \iff p_1^{\nu_1} p_2^{\nu_2}\cdots p_r^{\nu_r} \mid k p_1^{\nu_1-1} p_2^{\nu_2-1}\cdots p_r^{\nu_r-1}$

$\iff p_1p_2\cdots p_r \mid k$.

Therefore, by definition of $\Phi_m$,  $\Phi_{m}(\zeta^{n/m}) = \Phi_{m}(\xi) = 0$. 

The hypotheses of the lemma  are satisfied, thus

$$\Phi_n(x) = \Phi_{m}(x^{n/m})$$

\item[(b)]
We show that $\Phi_{2n}(x) = \Phi_n(-x)$ ($n>1, n$ odd, so $n\geq 3$).


Note first that $\deg(\Phi_{2n}(x)) = \phi(2n) = \phi(2) \phi(n) = \phi(n) = \deg(\Phi_n(-x))$.

If $n>2$, then $\phi(n)$ is even. Indeed, we can group in pairs the elements of $(\mathbb{Z}/ n \mathbb{Z})^*$, with the pairs $\{[d],-[d]\}$, where $d \wedge n = 1$ and $ [d] \neq -[d]$ since $(n \mid 2d , d \wedge n = 1) \Rightarrow n \mid 2$, which is impossible if $n > 2$. Hence
$$ (-1)^{\phi(n)} = 1\qquad (n>2).$$

$\Phi_{2n}(x)$ is monic by definition, and the leading coefficient of $\Phi_n(-x)$ is $(-1)^{\phi(n)} = 1$, so $\Phi_n(-x)$ is also monic.

Let $\alpha$ be any root of $\Phi_n(-x)$. Then $\alpha = -\zeta$, where $\zeta$ is a $n$th primitive root of unity, so $\zeta$ is an element of order $n$ in the group $\mathbb{C}^*$.

Then the order of $\alpha = -\zeta$ is $2n$. Indeed, for all $k \in \mathbb{Z}$,

$(-\zeta)^k = 1$, that is  $(-1)^k \zeta^k = 1$, implies $\zeta^{2k} = 1$, thus  $n \mid 2k$, so  $n \mid k$ (since $n$ is odd), therefore $\zeta^k = 1, (-1)^k = 1$ and so  $2\mid k$.

As $n \wedge 2 = 1, 2n \mid k$.

Conversely, if $2n \mid k, (-\zeta)^{2n} = [(-1)^2]^n [\zeta^n]^2 = 1$.

Conclusion: $(-\zeta)^k = 1 \iff 2n \mid k$, so the order of $\alpha = -\zeta$ is $2n$, hence $x = -\zeta$  is a root of $\Phi_{2n}$.

Every root of $\Phi_n(-x)$ in $\C$  is a root of $\Phi_{2n}(x)$. Moreover $\Phi_n(-x)$  is a separable polynomial, and $\deg(\Phi_{2n}(x)) = \deg(\Phi_n(-x))$.  Then the lemma gives the conclusion, for all odd $n$, $n>1$,

$$\Phi_{2n}(x) = \Phi_n(-x)$$

\item[(c)]

We show first that $\Phi_n(x)$ divides $\Phi_n(x^p)$. As $\Phi_n(x)$ is separable, it is sufficient to verify that every root $\zeta$ of $\Phi_n(x)$ is a root of $\Phi_n(x^p)$. Such a root   $\zeta$  is a $n$th primitive root of unity, so its order is $n$. Then the order of $\zeta^p$ is also $n$. Indeed, for all $k\in \Z$, as $n\wedge p = 1$,
$$(\zeta^p)^k=1 \iff \zeta^{pk} = 1 \iff n \mid pk \iff n \mid k.$$
Therefore $\zeta^p$ is a root of $\Phi_n$, so $\Phi_n(\zeta^p)=0$ and $\zeta$ is a root of $\Phi_n(x^p)$.
$$\Phi_n(x) \mid \Phi_n(x^p)\quad (p\nmid n).$$

We compare the degrees: 

$\deg(\Phi_{pn}(x)) = \phi(pn) =\phi(p)\phi(n) = (p-1)\phi(n)$,

$\deg(\Phi_n(x^p)/\Phi_n(x)) = p \phi(n) - \phi(n) = (p-1)\phi(n)$, 
thus
$$\deg(\Phi_n(x^p)/\Phi_n(x)) = \deg(\Phi_{pn}(x)).$$
Moreover, these two polynomials are monic, and $\Phi_{pn}$ is separable.

We show that every root $\zeta$ of $\Phi_{pn}(x)$ is a root of $\Phi_n(x^p)/\Phi_n(x)$.

If $\zeta$ is a root of $\Phi_{pn}(x)$, then $o(\zeta) = pn$, therefore $o(\zeta^p) = n$ 

(indeed, for all $k\in \Z$, $ (\zeta^p)^k = 1 \iff \zeta^{pk}=1 \iff pn \mid pk \iff n \mid k$).

So $\zeta^p$ is a root of $\Phi_n(x)$, which is equivalent to $\zeta$ is a root of $\Phi_{n}(x^p)$.

As $o(\zeta) = pn$, $\zeta^n \neq 1$, $\Phi_n(\zeta)\neq 0$, therefore $\zeta$ is a root of $\Phi_{n}(x^p)/\Phi_n(x)$.

The hypotheses of the lemma are so satisfied, so 

$$\Phi_{pn}(x) = \Phi_n(x^p)/\Phi_n(x) \qquad (p\nmid n).$$

\end{enumerate}
\end{proof}

\paragraph{Ex. 9.1.13}

{\it We know $\Phi_p(x)$ when $p$ is prime. Use this and Exercise 12 to compute $\Phi_{15}(x)$ and $\Phi_{105}(x)$.
}

\begin{proof}
\begin{enumerate}
\item[(a)]
By Exercise 12(c), 
\begin{align*}
\Phi_{15}(x) &= \frac{\Phi_3(x^5)}{\Phi_3(x)}\\
&=\frac{x^{10} +x^5+1}{x^2+x+1}\\
&=x^8 -x^7+x^5 -x^4+x^3 -x+1.
\end{align*}

\item[(b)]
\begin{align*}
\Phi_{105}(x) &= \frac{\Phi_{15}(x^7)}{\Phi_{15}(x)}\\
=& \frac{x^{56} -x^{49}+x^{35} -x^{28}+x^{21} -x^7+1}{x^8 -x^7+x^5 -x^4+x^3 -x+1}\\
=&\quad x^{48} + x^{47} + x^{46} - x^{43} - x^{42} - 2 \, x^{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}\\
  &- 2 \, x^{7} - x^{6} - x^{5} + x^{2} + x + 1
\end{align*}

\end{enumerate}
\end{proof}

\paragraph{Ex. 9.1.14}

{\it The M\"obius function is defined for integers $n\geq 1$ by
$$
\mu(n) = 
\left\{
\begin{array}{ll}
  1&    \mathrm{if} \ n=1,  \\
  (-1)^s,& \mathrm{if}\ n =p_1\cdots p_s\  \mathrm{for}\  \mathrm{distinct}\ \mathrm{primes}\ p_1, \ldots,p_s    \\
  0,    &   \mathrm{otherwise}
\end{array}
\right.
$$
Prove that $\sum_{d \mid n} \mu\left(\frac{n}{d}\right) = 0$ when $n>1$.
}

\begin{proof}
Suppose $n>1$.  Write $n =p_1^{\alpha_1} p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ its decomposition in prime factors. The factors $d$ of $n$ such that $\mu(d) \ne 0$ are the integers $d = p_1^{\beta_1} p_2^{\beta_2}\cdots p_k^{\beta_k}$ where $\beta_i = 0,1$. If exactly $r$  exponents $\beta_i$ are non zero, then $\mu(d) = (-1)^r$, and there are  $\binom{k}{r}$ such integers $d$.
 
Therefore $$\sum_{d \vert n} \mu(d) = \sum_{r=0}^{k} (-1)^r \binom{k}{r} = (1-1)^k = 0 $$ (since $k \not = 0$)
 
  
 Conclusion: if $n \geq 1$,
 $$\sum_{d \mid n} \mu\left(\frac{n}{d}\right) = \sum_{d \vert n} \mu(d)= 
 \left\{
\begin{array}{ll}
  0,&    \mathrm{if} \ n>1,  \\
  1,   &   \mathrm{if}\ n=1.
\end{array}
\right.
$$
\end{proof}

\paragraph{Ex. 9.1.15}

{\it Let $\mu$ be the M\"obius function defined in Exercise 14. Prove that
$$\Phi_n(x) = \prod_{d\mid n} (x^d-1)^{\mu(n/d)}.$$
}

\begin{proof}
Our starting point is $$F(n) = x^n - 1 = \prod\limits_{ d \mid n} \Phi_d \hspace{1cm} (n \geq 1).$$
It is sufficient to copy the proof of the M\"obius Inversion Formula in multiplicative notations:
\begin{align*}
   \prod_{d \mid n} (x^d - 1)^{\mu \left (\frac{n}{d} \right )} &=  \prod\limits_{e \vert n}  (x^{\frac{n}{e}} -1)^{\mu(e)}\\
           &= \prod\limits_{e \vert n} \ \prod\limits_ {d \vert \frac{n}{e}} \Phi_d^{ \mu(e) } \\
            &=\prod\limits_{d \vert n}\  \prod_{e \vert \frac{n}{d}}\Phi_d^{\mu(e)}
            			\hspace{1cm} (\mathrm{ since }\  e\vert n \  \mathrm{and}   \ d \vert \frac{n}{e}  \iff d \vert n\  \mathrm{and}  \ e \vert \frac{n}{d}) \\
           & = \prod\limits_{d \vert n}   \Phi_d^{\sum\limits_{\ e \vert \frac{n}{d}}\mu(e)} \\
           &= \Phi_n,
 \end{align*}         
           since by Exercise 14, $\sum_{\ e \vert \frac{n}{d}} \mu(e) \not = 0$ only if $\frac{n}{d}=1$, that is $d =n$, so the product is $\Phi_n$.

Conclusion :            
$$\Phi_n(x) = \prod\limits_{d \mid n} (x^d - 1)^{\mu \left (\frac{n}{d} \right )}\quad (n\geq 1).$$
\end{proof}

\paragraph{Ex. 9.1.16}

{\it Let $n$ and $m$ be relatively prime positive integers.
\be
\item[(a)] Prove that $\Q(\zeta_n,\zeta_m) = \Q(\zeta_{nm})$.
\item[(b)] Prove that $\Phi_n(x)$ is irreducible over $\Q(\zeta_m)$.
\ee
}

\begin{proof}
Here we write $\zeta_k = e^{2i\pi/k}$ for all subscript $k$.
\begin{enumerate} 
\item[(a)]
$\zeta_n = (\zeta_{nm})^m \in \Q(\zeta_{nm})$, and $\zeta_m = (\zeta_{nm})^n \in \Q(\zeta_{nm})$,therefore
$$\Q(\zeta_n,\zeta_m) \subset \Q(\zeta_{nm}).$$

As $n\wedge m = 1$, there exists integers $u,v$ such that $1=un+vm$.

Therefore $\zeta_{nm} = (\zeta_{nm}^n)^u (\zeta_{nm}^m)^v = \zeta_m^u \zeta_n^v \in \Q(\zeta_n,\zeta_m)$, hence
$$\Q(\zeta_{nm})\subset\Q(\zeta_n,\zeta_m)$$ 
We have proved
$$\Q(\zeta_{nm})=\Q(\zeta_n,\zeta_m)$$ 


\begin{center}
\begin{tikzpicture}
    \node (nm) at (4,4) {$\Q(\zeta_n,\zeta_m)$};
    \node (n) at (2,2) {$\Q(\zeta_n)$};
     \node (m) at (6,2) {$\Q(\zeta_m)$};
    \node (Q) at (4,0) {$\Q$};
    \draw[->] (Q) edge (n)  edge (m);
    \draw[<-] (nm) edge (n)  edge (m);
\end{tikzpicture}
\end{center}


\item[(b)]
By Corollary 9.1.10, $[\Q(\zeta_{nm}): \Q] = \phi(nm)$. As $n \wedge m=1, \phi(nm) = \phi(n) \phi(m)$ (Lemma 9.1.1), so
$[\Q(\zeta_{nm}) : \Q] = \phi(n)\phi(m)$, and by part (a), this is equivalent to
$$[\Q(\zeta_n, \zeta_m) : \Q] = \phi(n)\phi(m).$$
Using the Tower Theorem,  
$$\phi(n)\phi(m) = [\Q(\zeta_n, \zeta_m) : \Q] = [\Q(\zeta_n, \zeta_m) : \Q(\zeta_m)]\, [\Q( \zeta_m) : \Q] = \phi(m)[\Q(\zeta_n, \zeta_m) : \Q(\zeta_m)] ,$$thus
$$\phi(n) = [\Q(\zeta_m)( \zeta_n) : \Q(\zeta_m)] .$$

Let $f$ be the minimal polynomial of $\zeta_n$ over $\Q(\zeta_m)$. Then $$\deg(f) = [\Q(\zeta_m)( \zeta_n) : \Q(\zeta_m)] = \phi(n).$$

$\zeta_n$ is a root of $\Phi_n(x)\in \Q[x] \subset \Q(\zeta_m)[x]$, therefore $f \mid \Phi_n$ in $\Q(\zeta_m)[x]$. Moreover these two polynomials are monic of same degree $\phi(n)$, so they are identical. $\Phi_n = f$ is so irreducible over $\Q(\zeta_m)$.
\end{enumerate}
\end{proof}

\subsection{GAUSS AND ROOTS OF UNITY (OPTIONAL)}

\paragraph{Ex. 9.2.1}

{\it Let $G$ be a cyclic group of order $n$ and let $g$ be a generator of $G$.
\be
\item[(a)] Let $f$ be a positive divisor of $n$ and set $e = n/f$. Prove that $H_f = \langle g^e \rangle$ has order $f$ and hence is the unique subgroup of order $f$.

\item[(b)] Let $f$ and $f'$ be positive divisors of $p-1$. Prove that $H_f \subset H_{f'}$ if and only if $f \mid f'$.
\ee
}

\begin{proof}
\begin{enumerate}
\item[(a)]
$\bullet$ Let $G$ be a cyclic group of order $n$ and let $g$ be a generator of $G$. If $f$ is a positive divisor of $n$, write $e = n/f$, and $H = \langle g^e\rangle$.

The order of $g$ is $n = ef$, hence the order of $g^e$ is $\frac{n}{n\wedge e} = \frac{n}{e} = f$, therefore the set  $A = \{(g^e)^0,\cdots, (g^e)^{f-1}\} \subset \langle g^e \rangle$ has $f$  distinct elements: $\vert A \vert = f$. 

Conversely, if $h \in \langle g^e\rangle$, then $h = (g^e)^k, k \in \Z$.
The Euclidean division of $k$ by $f$ gives $k = qf+r, 0 \leq r <f$, thus $h = (g^{ef})^q g^{er} = ({g^e})^r, 0 \leq r <f$, therefore $h \in A$. 
 
Hence $H_f = \langle g^e \rangle = A$ has order  $f$.
$$\vert H_f\vert = \vert \langle g^e \rangle \vert = f.$$

\bigskip

$\bullet$ Let $K$ be any subgroup of order $f$. We must prove that $K = H$.

The set $E$ of integers $m>0$ such that $g^m \in K$ is non empty, since $g^n=e \in K$. Set
$$k = \min(E) =  \min\{m \in \N^*\  \vert \ g^m \in K\},$$
so $k$ is the least positive integer such that $g^k \in K$. We show that $K = \langle g^k \rangle$.

As $g^k \in K, \langle g^k \rangle \subset K$.

Conversely, if $h \in K$, then $h$ is an element of $G$ of the form $h=g^l, \ l\in \Z$. The Euclidean division of $l$ by $k$ gives $l = qk+r, \ 0 \leq r<k$.

Then $g^r = g^l(g^k)^{-q} = h (g^k)^{-q} \in K$ and $0\leq r < k$. If $r$ was not zero, it would lie in $E$ and would be less than the minimum of $E$. This is a contradiction, so $r=0$, and $h = g^l =(g^k)^{q} \in \langle g^k \rangle$. Therefore $K \subset \langle g^k  \rangle$. Finally,
$$K = \langle g^k \rangle.$$

We show first that $k \mid n$. Write $d = k\wedge n$. There exist integers $u,v$ such that $d = uk+vn$, therefore $g^d =(g^k)^u (g^n)^v= (g^k)^u \in K$, so $d \in E$, and $1 \leq d \leq k$, therefore $d = k$ by definition of $k = \min(E)$. So $k = k \wedge n$, hence $k \mid n$.

$K = \langle g^k \rangle$ is cyclic, and its cardinality is the order of $g^k,\  k\mid n$,  so
$$  |K| = \langle g^k \rangle = o(g^k)= \frac{n}{k},$$
by the first part of the proof.

By hypothesis the order of $K$ is $f$, so $f = \vert K \vert =n/k$, and $k= n/f= e$.$$K = \langle g^e \rangle = H.$$

Conclusion: 

A cyclic group with generator $g$, of order $n=ef$, contains a unique subgroup of order $f$, written $H_f$, which is cyclic, generated by $g^e$.


\item[(b)]
Let $f,f'$ be positive divisors of $p-1 = |(\Z/p\Z)^*|$, and let $g$ a generator of $(\Z/p\Z)^*$. As in the text, write $H_f$ the unique subgroup of $(\Z/p\Z)^*$ of order $f$.

If $H_f \subset H_f'$, then $H_f$ is a subgroup of $H_f'$. By Lagrange's Theorem  $\vert H_f \vert$ divides $\vert H_{f'} \vert$, so $f \mid f'$.

Conversely, if $f \mid f'$, $f' = q f, \ q \in \N$. Moreover $H_f = \langle g^e \rangle, H_{f'}= \langle g^{e'} \rangle$, where $n = ef =e'f'$ by part (a). Therefore $e = e'q$, and $g^e = (g^{e'})^q \in H_{f'}$, hence $H_f = \langle g^e \rangle \subset H_{f'}$.
$$f \mid f' \iff H_f \subset H_{f'}.$$
\end{enumerate}
\end{proof}

\paragraph{Ex. 9.2.2}

{\it Prove Proposition 9.2.1.
}

\begin{proof}
Write $\tilde{H}_f$ the subgroup corresponding to $H_f$ by the isomorphism $\Gal(\Q(\zeta_p)/\Q) \simeq (\Z/p\Z)^*$. Then

$$\sigma \in \tilde{H}_f \iff \exists [i] \in H_f, \ \sigma(\zeta_p) = \zeta_p^i,$$ and

$$L_f = \{\alpha \in \Q(\zeta_p)\ \vert \ \forall \sigma \in  \tilde{H}_f, \ \sigma(\alpha) = \alpha\}$$
is the fixed field of  $\tilde{H}_f$, with  $ \Q\subset L_f \subset \Q(\zeta_p)$.

\begin{enumerate}
\item[(a)]
As $G = \Gal(\Q(\zeta_p)/\Q)$ is Abelian ($G$ is cyclic since $(\Z/p\Z)^* \simeq G$ is cyclic for prime $p$), so every subgroup of $G$ is normal, therefore  $\Q\subset L_f$ is a Galois extension (Theorem 7.3.2).

 Moreover, by the Galois correspondence (Theorem 7.3.1), $[L_f : \Q] = (G:\tilde{H}_f), $ and $(G:\tilde{H}_f) = ((\Z/p\Z)^* : H_f) = (p-1)/f = e$, so
$$[L_f : \Q]=e.$$
$L_f$ is a Galois extension of $\Q$ of degree $e$.
\item[(b)]
By Exercise 1, $f \mid f' \iff  H_f \subset H_{f'}$. 
As the Galois correspondence is order reversing,
$$f \mid f' \iff  H_f \subset H_{f'} \iff \tilde{H}_f \subset \tilde{H}_{f'} \iff L_f \supset L_{f'}.$$

\item[(c)]
Let $f,f'$ be positive divisors of $p-1$ such that $f \mid f'$. Since $G$ is Abelian,  $L_{f'} \subset L_f$ is a Galois extension, and by Theorem 7.3.2, 
$$\Gal(L_f/L_{f'}) \simeq \Gal(\Q(\zeta_p)/L_{f'}) / \Gal(\Q(\zeta_p)/L_f) = \tilde{H}_{f'} / \tilde{H}_{f} \simeq H_{f'} / H_f.$$

As $H_{f'}$ is cyclic of order $f'$, the quotient group $H_{f'} / H_{f}$ is itself cyclic, of order $f'/f$.

Conclusion:
\begin{center}
$\Gal(L_f/L_{f'})$ is cyclic of order $f'/f$.
\end{center}
\end{enumerate}
\end{proof}

\paragraph{Ex. 9.2.3}

{\it Let $\eta_1,\eta_2,\eta_3$ be as in Example 9.2.2.
\be
\item[(a)] We know that $\zeta_7$ is a root of $x^6+x^5+x^4+x^3+x^2+x+1 = 0$. Dividing by $x^3$ gives
$$x^3+x^2+x+1+x^{-1}+x^{-2}+x^{-3} = 0.$$
Use this to show that $\eta_1,\eta_2,\eta_3$ are roots of $y^3+y^2-2y-1$.
\item[(b)] Prove that $[\Q(\eta_1):\Q] = 3$, and conclude that $\Q(\eta_1)$ is the fixed field of the subgroup $\{e,\tau\} \subset \Gal(\Q(\zeta_7)/\Q)$, where $\tau$ is the complex conjugation.
\item[(c)] Prove (9.10).
\ee}

\begin{proof}
\begin{enumerate}
\item[(a)]
Let $\zeta$ be any 7th primitive root of unity (i.e. $\zeta = \zeta_7^i, \ i=1,\cdots,6$).

Then $1+ \zeta+ \zeta^2 + \zeta^3+\zeta^4+\zeta^5+\zeta^6 = 0$, and  division by $\zeta^3$ gives
\begin{align}
\zeta^{-3} + \zeta^3 + \zeta^{-2}+ \zeta^2+\zeta+\zeta^{-1}+1 = 0. \label{eq:1}
\end{align}

Write $\eta = \zeta+\zeta^{-1}$. Then
\begin{align*}
\eta^2 & = \zeta^2+ \zeta^{-2}+2,\\
\eta^3 &= \zeta^3+\zeta^{-3} + 3(\zeta+\zeta^{-1}).
\end{align*}
Therefore 
\begin{align*} 
\zeta^2+ \zeta^{-2} &= \eta^2-2,\\
 \zeta^3+\zeta^{-3} &= \eta^3 - 3 \eta.
 \end{align*}
By  \eqref{eq:1},
$ (\eta^3 - 3 \eta) +(\eta^2-2) + \eta + 1 = 0$, so
\begin{align}
\eta^3  + \eta^2 - 2 \eta - 1 = 0.\label{eq:2}
\end{align}
Applying the equality \eqref{eq:2} to $\zeta_7, \zeta_7^2, \zeta_7^3$, we obtain that $\eta_1= \zeta_7+\zeta_7^{-1}, \eta_2 = \zeta_7^2 + \zeta_7^{-2}, \eta_3 = \zeta_7^3+\zeta_7^{-3}$ are roots of 
$$f = x^3+x^2-2x-1.$$
As the minimal polynomial of $\zeta_7$ over $ \Q$ is $\Phi_7$ of degree 6, the list $(1,\zeta_7, \zeta_7^2,\zeta_7^3,\zeta_7^4,\zeta_7^5)$ is linearly independent over $\Q$, thus also the list obtained by multiplication by $\zeta_7$, so $(\zeta_7, \zeta_7^2,\zeta_7^3,\zeta_7^4,\zeta_7^5,\zeta_7^6)$ is a linearly independent list, therefore $\eta_1 = \zeta_7+ \zeta_7^6,\eta_2 = \zeta_7^2+\zeta_7^5,\eta_3 = \zeta_7^3+\zeta_7^4$ are linearly independent, so are a fortiori distinct. Therefore
$$f = x^3+x^2-2x-1 = (x- \eta_1)(x-\eta_2)(x-\eta_3).$$
$\eta_1,\eta_2,\eta_3$ are the three distinct roots of $f$.

\item[(b)]
$f$ has no root in $\Q$. Indeed, if $\alpha = p/q, p\wedge q = 1$ was such a root, we would have the equality
$$p^3 + p^2q -2pq^2 -q^3=0,$$
which implies, since $p\wedge q= 1$, that $p \mid 1, q \mid 1$, so $\alpha = \pm1$, but neither $1$, nor $-1$ is a root of $f$.

Since $f$ has no root in $\Q$ and $\deg(f) = 3$, $f$ is irreducible over $\Q$. So $f$ is the minimal polynomial of $\eta_1$ over $\Q$, and also of $\eta_2,\eta_3$, which are so conjugate of $\eta_1$ over $\Q$. Moreover 
$$[\Q(\eta_1):\Q] = \deg(f) = 3.$$

Let $\tau$ be the complex conjugation restricted to $\Q(\zeta_7)$. As $\tau(\zeta_7)  = \overline{\zeta}_7 = \zeta_7^{-1} \in \Q(\zeta_7)$, $\tau$ is an automorphism of $\Q(\zeta_7)$ which fixes the elements of $\Q$, so $\tau \in \Gal(\Q(\zeta_7)/\Q)$, and $\tau^2 = e$, therefore $\{e,\tau\} = \tilde{H}_2$ is the unique subgroup of $G = \Gal(\Q(\zeta_7)/\Q)$ of order 2.

Let $L_2 = L_{\langle\tau\rangle}$ be the fixed field of $\tilde{H}_2$.
By the Galois Correspondence (see Proposition 9.2.1 and Exercise 2), 
$$[L_2 : \Q] = (G: H_2) =3.$$
As $\eta_1 \in \R, \tau(\eta_1) = \eta_1$, hence $\eta_1 \in L_2$, and so $\Q(\eta_1) \subset L_2$. 

Since $[L_2:\Q] = [\Q(\eta_1):\Q] = 3$, then $[L_2 : \Q(\eta_1)] = 1$, hence $L_2 = \Q(\eta_1)$.
\begin{center}
The fixed field $L_2$ of $\tilde{H}_2 = \{e,\tau\}$ is $\Q(\eta_1)$.
\end{center}

\item[(c)] $\eta_1=2 \cos(2\pi/7), \eta_2 = 2\cos(4\pi/7),\eta_3 = 4 \cos(6 \pi/7)$ are the roots of $f = x^3+x^2-2x-1$. We compute these roots with the Cardan's Formula.

The substitution $x=y-1/3$ in $f$ gives
\begin{align*}
g(y) &= f\left(y - \frac{1}{3}\right)\\
& = \left(y - \frac{1}{3}\right)^3+  \left(y - \frac{1}{3}\right)^2-2\left(y - \frac{1}{3}\right)-1\\
&=y^3-y^2+\frac{1}{3}y-\frac{1}{27}+y^2-\frac{2}{3}y+\frac{1}{9} - 2y +\frac{2}{3} - 1\\
&=y^3 - \frac{7}{3} y - \frac{7}{27}
\end{align*}
(Note: if $\Delta$ is the discriminant of $f$ or $g$, then $\Delta = -4p^3-27q^2 = -4\left(-\frac{7}{3}\right)^3 - 27 \left(\frac{7}{27}\right)^2 = \frac{1372}{27} - \frac{49}{27} = \frac{1323}{27} = 49 = 7^2$ is the square of an element of $\Q$, hence the Galois group of $f$ is $A_3\simeq \Z/3\Z$. This shows again that $$\vert \Gal(\Q(\eta_1) / \Q) \vert = [L_2 : \Q] = 3.)$$

Let $\alpha$ a root of $g$ (that is to say $\alpha - 1/3$ is a root of $f$). There exist two complex numbers $u,v$ such that
$\alpha = u+v, uv = 7/9$. Then
\begin{align*}
0 &= (u+v)^3 -\frac{7}{3}(u+v) - \frac{7}{27}\\
&=u^3+v^3+\left(3uv-\frac{7}{3} \right)(u+v) -\frac{7}{27}\\
&=u^3+v^3 -\frac{7}{27}\\
\end{align*}
So $(u,v)$, which satisfies the condition $uv = 7/9$, is a solution of the system
\begin{align*}
u^3+v^3 &= \frac{7}{3^3}\\
u^3v^3&= \frac{7^3}{3^6}
\end{align*}
$u^3,v^3$ are so the roots of the equation $x^2-\frac{7}{3^3}x+ \frac{7^3}{3^6}$, of discriminant $$\delta = \frac{7^2}{3^6} - 4 \frac{7^3}{3^6}= \frac{7^2(-27)}{3^6} =-\frac{7^2}{3^3} = -\frac{49}{27}.$$
\begin{align*}
u^3 &= \frac{1}{2}\left(\frac{7}{27} + i \sqrt{\frac{49}{27}} \right) = \frac{1}{27} \times \frac{7}{2} \left(1 + 3i\sqrt{3} \right)\\
v^3 &= \frac{1}{2}\left(\frac{7}{27} - i \sqrt{\frac{49}{27}} \right)= \frac{1}{27} \times \frac{7}{2} \left(1 - 3i\sqrt{3} \right)\\
\end{align*}
As $u^3 = \overline{v}^3$, and $uv = 7/9 \in \R$, then $v = \omega^k \overline{u},\ k = 0,1,2$, and so $uv = u \overline{u} \omega^k \in \R$, therefore $\omega^k \in \R$ , so $k=0$, which gives  $v= \overline{u}$.
The set $\{\eta_1,\eta_2,\eta_3\}$ of the three roots of $f$ is so the set $\{-1/3+ u+\overline{u},-1/3+ \omega u + \omega^2\overline{u},-1/3+ \omega^2 u +\omega \overline{u}\}$.

To identify each root, we must define the determination of $3u = \sqrt[3]{\frac{7}{2} \left(1 + 3i\sqrt{3} \right)}$. Choose for this cubic root the one which lies in the first  quadrant (there exists one and only one such a cubic root since $\mathrm{Arg}(1+3i\sqrt{3}) \in [0,\pi/2]$), and write $3 \overline{u} = \sqrt[3]{\frac{7}{2} \left(1 - 3i\sqrt{3} \right)}$ its conjugate.

Then
\begin{align*}
-\frac{1}{3} + u + \overline{u} &= \frac{1}{3}(-1+3u+3\overline{u})\\
&=\frac{1}{3}\left(-1+\sqrt[3]{\frac{7}{2} \left(1 + 3i\sqrt{3} \right)}+\sqrt[3]{\frac{7}{2} \left(1 - 3i\sqrt{3} \right)}\right)\\
\end{align*}
As $\left \vert \frac{7}{2}\left(1+3i\sqrt{3}\right)\right \vert = \frac{7}{2} \sqrt{28} =(\sqrt{7})^3$, then
 $\vert 3u\vert = \sqrt{7}$, and $\mathrm{Arg}(3u)\in [0,\pi/6]$, therefore $\re(3u)\geq \sqrt{7}\cos(\pi/6) = \sqrt{7}\sqrt{3}/2$, so $2\re(3u) \geq \sqrt{21}$.

Therefore $\re(-1+3u+3\overline{u}) \geq \sqrt{21} -1 >0$.

As $\eta_1 = 2\cos(2\pi/7)$ is the only positive root of $f$,

$$\eta_1 = \zeta_7+\zeta_7^{-1} =2 \cos(2\pi/7) =  \frac{1}{3}\left(-1+\sqrt[3]{\frac{7}{2} \left(1 + 3i\sqrt{3} \right)}+\sqrt[3]{\frac{7}{2} \left(1 - 3i\sqrt{3} \right)}\right)$$
where $\sqrt[3]{\frac{7}{2} \left(1 + 3i\sqrt{3} \right)}$ is chosen such that
$$\re\left(\sqrt[3]{\frac{7}{2} \left(1 + 3i\sqrt{3} \right)}\right)>0, \im\left(\sqrt[3]{\frac{7}{2} \left(1 + 3i\sqrt{3} \right)}\right)>0$$
and $\sqrt[3]{\frac{7}{2} \left(1 - 3i\sqrt{3} \right)}$ is its conjugate.

As $\zeta_7$ is a root of $x^2-\eta_1x +1$, with positive imaginary part, then $\zeta_7 = \frac{1}{2}\left(\eta_1 + i \sqrt{4 - \eta_1^2}\right)$, so
\begin{align*}
\zeta_7 &= -\frac{1}{6} + \frac{1}{6} \sqrt[3]{\frac{7}{2}(1+3i\sqrt{3})} + \frac{1}{6} \sqrt[3]{\frac{7}{2}(1-3i\sqrt{3})}\\
&\phantom{--}+\frac{i}{2} \sqrt{4 - \left ( \frac{1}{3} - \frac{1}{3} \sqrt[3]{\frac{7}{2}(1+3i\sqrt{3})} - \frac{1}{3} \sqrt[3]{\frac{7}{2}(1-3i\sqrt{3})}\right)^2}\\
&= -\frac{1}{6} + \frac{1}{6} \sqrt[3]{\frac{7}{2}(1+3i\sqrt{3})} + \frac{1}{6} \sqrt[3]{\frac{7}{2}(1-3i\sqrt{3})}\\
&\phantom{--}+i \sqrt{1 - \left ( \frac{1}{6} - \frac{1}{6} \sqrt[3]{\frac{7}{2}(1+3i\sqrt{3})} - \frac{1}{6} \sqrt[3]{\frac{7}{2}(1-3i\sqrt{3})}\right)^2}
\end{align*}
with the same cube roots.

(It seems that there is a misprint in (9.11)).
\end{enumerate}
\end{proof}

\paragraph{Ex. 9.2.4}

{\it Let $A\subset B$ be subgroups of a group $G$, and assume that $A$ has index $d$ in $B$. Prove that every left coset of $B$ in $G$ is a disjoint union of $d$ left cosets of $A$ in $G$.
}

\begin{proof}
Let $\{b_1\cdots,b_d\}$ a complete system of representatives of left cosets of $A$ in $B$, where $d=(B:A)$. Then
$$B = \biguplus_{1\leq i \leq d} b_i A.$$

If $cB,\ c\in G$, is any left coset of $B$ in $G$, then
$$cB = \biguplus_{1\leq i \leq d} c b_i A.$$
Indeed, 
\be
\item[$\bullet$] $b_i A \subset B$, thus $cb_iA \subset cB$, $i=1,\ldots,d$, therefore $\bigcup_{1\leq i \leq d} c b_i A \subset cB$.

\item[$\bullet$] If $g \in cB$, then $g = ch,\ h\in B$, and $h \in  b_i A$ for some $i, \ 1\leq i \leq d$, so $h= b_ia, a\in A$, hence $g = cb_i A \in \bigcup_{1\leq i \leq d} c b_i A$ . Therefore $cB \subset \bigcup_{1\leq i \leq d} c b_i A$.
$$cB = \bigcup_{1\leq i \leq d} c b_i A.$$
\item[$\bullet$] The union is a disjoint union: if $g \in cb_iA$ and $g\in cb_jA$, then $c^{-1}g \in b_iA\cap b_jA$, which is possible only if $i=j$. Thus $i\neq j \Rightarrow cb_iA\cap cb_jA = \emptyset$.
\ee
Conclusion: every left coset of $B$ in $G$ is the disjoint union of $d = (B:A)$ left cosets of $A$ in $G$.
\end{proof}

\paragraph{Ex. 9.2.5}

{\it Complete the proof of Proposition 9.2.8.
}

\begin{proof}

By Exercise 4 , we obtain (9.12):
$$[\lambda]H_{f'} = [\lambda_1]H_f\cup\cdots \cup[\lambda_d]H_f, \qquad \lambda = \lambda_1.$$
We must prove that every period $(f,\lambda_j),\ j=1,\ldots,d,$ is of the form  $(f,\lambda_j) = \sigma(\eta) = \sigma((f,\lambda))$, where $\sigma \in \Gal(\Q(\zeta_p)/L_{f'})$.

Write $[i] = [\lambda]^{-1} [\lambda_j]$.  As  $[\lambda_j]\in [\lambda] H_{f'}$, then  $[i] = [\lambda]^{-1} [\lambda_j ]\in H_{f'}$. 

Since $[\lambda_j ]= [ i \lambda] $,
 $$(f,\lambda_j) = (f,i\lambda), \qquad i\in H_{f'}.$$ 
Let $\sigma \in \Gal(\Q(\zeta_p)/L_{f'})$ be defined by $\sigma(\zeta_p) = \zeta_p^i$, where $ [i] \in H_{f'}$, so by Lemma 9.2.4(c),
$$(f,\lambda_j) = (f,i\lambda) = \sigma(\eta),\ \sigma \in  \Gal(\Q(\zeta_p)/L_{f'}).$$
Every $(f,\lambda_j),\ j=1,\ldots,d,$ is a conjugate of $(f,\lambda)$ over $L_{f'}$.
\end{proof}

\paragraph{Ex. 9.2.6}

{\it Prove that the sum of the distinct $f$-periods equals $-1$.
}

\begin{proof}
With a fixed divisor $f$ of $n$, and $e = n/f$,  
$$(\Z/p\Z)^* = \biguplus_{1\leq i \leq e} \lambda_i H_f,$$ 
where $\lambda_1,\cdots,\lambda_e$ are distinct representatives of the cosets of $H_f$ in $(\Z/p\Z)^*$.

The $e$ distinct $f$-periods are the $(f,\lambda_i),\ i=1,\cdots,e$, thus  
$$\sum_{i=1}^e (f,\lambda_i) = \sum_{i=1}^e \sum_{a\in [\lambda_i] H_f} \zeta_p^a =  \sum_{a\in \bigcup_{1\leq i \leq e} [\lambda_i] H_f} \zeta_p^a = \sum_{a\in (\Z/p\Z)^*} \zeta_p^a = -1,$$

since $\sum_{a\in (\Z/p\Z)} \zeta_p^a = 0$.
\end{proof}

\paragraph{Ex. 9.2.7}

{\it This exercise is concerned with the details of Examples 9.2.10, 9.2.11, 9.2.12, and 9.2.13.
\be
\item[(a)] Show that $2$ is a primitive root modulo $19$.
\item[(b)] Use the methods of Example 9.2.10 to obtain formulas for $(6,2)^2$ and $(6,4)^2$.
\item[(c)] Show that the formulas of part (b) follow from $(6,1)^2 = 4 -(6,2)$ and part (d) of Lemma 9.2.4.
\item[(d)] Prove (9.15) and use this and Exercise 6 to show that $(6,1)(6,2)(6,4) = 7$.
\item[(e)] Find the minimal polynomial of $(3,2)$ and $(3,4)$ over the field $L_6$ considered in Example 9.2.12.
\item[(f)] Show that (9.18) is the minimal polynomial of $\zeta_{19}$ over the field $L_3$ considered in Example 9.2.13.
\ee
}

\begin{proof}
\begin{enumerate}
\item[(a)]
$2^2=4\not \equiv 1\pmod {19}$, and $2^9=512 = 19\times26+18 \equiv -1\pmod{19}$. Therefore the order of $[2]$ in $(\Z/19\Z)^*$ is 1$8$, so $2$ is a primitive root modulo $19$.


\item[(b)]
In Example 9.2.10, we obtained
\begin{align*}
H_6 &= \{1,7,8,11,12,18\},\\
2H_6&=\{2,3,5,14,16,17\},\\
4H_6 &= \{4,6,9,10,13,15\}.\\
\end{align*}
Verification with Sage:
\begin{verbatim}
a = Mod(8,19)
lc = [sorted([2^j * a^i for i in range(6)]) for j in range(3)]; print(lc)
[[1, 7, 8, 11, 12, 18], 
 [2, 3, 5, 14, 16, 17], 
 [4, 6, 9, 10, 13, 15]]
\end{verbatim}

By Proposition 9.2.9, with $(6,19) = (6,0) = 6$,
$$(6,1)^2 = \sum_{\lambda'\in H_6}(6,\lambda'+1),\ (6,2)^2 = \sum_{\lambda'\in 2H_6}(6,\lambda'+2),\ (6,4)^2 = \sum_{\lambda'\in 4H_6}(6,\lambda'+4).$$
\begin{align*}
(6,1)^2 &=(6,2)+(6,8)+(6,9)+(6,12)+(6,13)+6\\
&=2(6,1)+(6,2)+2(6,4)+6\\
&=(6,1)+(6,4)+5\\
&=4 - (6,2),\\
\\
(6,2)^2&=(6,4)+(6,5)+(6,7)+(6,16)+(6,18)+6\\
&=2(6,1)+2(6,2)+(6,4)+6\\
&=(6,1)+(6,2)+5\\
&=4-(6,4),\\
\\
(6,4)^2&=(6,8)+(6,10)+(6,13)+(6,14)+(6,17)+6\\
&=(6,1)+2(6,2)+2(6,4)+6\\
&=(6,2)+(6,4)+5\\
&=4-(6,1).
\end{align*}

$$(6,1)^2= 4 - (6,2),\ (6,2)^2 = 4-(6,4),\ (6,4)^2 = 4 - (6,1).$$

If we write $\eta_1= (6,1), \eta_2 = (6,2), \eta_3 = (6,4)$, then
$$\eta_1^2 = 4 - \eta_2,\quad \eta_2^2 = 4 - \eta_3, \quad \eta_3^2 = 4 - \eta_1.$$


\item[(c)]
The similarity of these results has an explanation. If $\sigma \in G=\Gal(\Q(\zeta_{19})/\Q)$ is determined by $\sigma(\zeta_{19}) = \zeta_{19}^2$, then by Lemma 9.2.4(d), 
$\sigma((6,1)) = (6,2), \sigma((6,2)) = (6,4)$ and $\sigma((6,4)) = (6,8) = (6,1)$, so

$$\sigma(\eta_1) = \eta_2,\quad  \sigma(\eta_2) = \eta_3,\quad  \sigma(\eta_3) = \eta_1.$$
Therefore $\eta_1^2 = 4 - \eta_2$ implies $\eta_2^2 = 4 - \eta_3$ and $\eta_3^2 = 4 - \eta_1$.

By Proposition 9.2.6 and Corollary 9.2.7, $L_6=\Q(\eta_1) =\Q(\eta_1,\eta_2,\eta_3)=\mathrm{Vect}_{\Q}(\eta_1,\eta_2,\eta_3)$, and so $\sigma$ sends $L_6$ on itself. The restriction $\tilde{\sigma}$ of $\sigma$ to $\Q(\eta_1)$ is so a $\Q$-automorphism of $\Q(\eta_1)$ of order 3, since $\tilde{\sigma}^3(\eta_1) = \eta_1$. Moreover, the extension $\Q \subset \Q(\eta_1)$ is Galois (since $G = \Gal(\Q(\zeta_{19}/\Q)$ is Abelian, every subgroup of $G$ is normal), so
$$\Gal(\Q(\eta_1)/\Q) \simeq \Gal(\Q(\zeta_{19})/\Q) / \Gal(\Q(\zeta_{19})/\Q(\eta_1)),$$
thus $$\vert \Gal(\Q(\eta_1)/\Q) \vert = [\Q(\eta_1):\Q] =(G :\tilde{H}_6) = ((\Z/19\Z)^*:H_6) = 3,$$ therefore
$$\Gal(\Q(\eta_1)/\Q) \simeq \Z/3\Z, \ \Gal(\Q(\eta_1)/\Q) = \langle \tilde{\sigma} \rangle.$$


\item[(d)]
\begin{align*}
(6,1)(6,2)&=\sum_{\lambda'\in H_6} (6,\lambda'+2)\\
&=(6,3)+(6,9)+(6,10)+(6,13)+(6,14)+(6,1)\\
&=(6,2)+(6,4)+(6,4)+(6,4)+(6,2)+(6,1)\\
&=(6,1)+2(6,2)+3(6,4).\\
\end{align*}
If we apply  ${\sigma},{\sigma}^2$ to this equality, we obtain (9.15) :
\begin{align*}
(6,1)(6,2) &=(6,1)+2(6,2)+3(6,4),\\
(6,2)(6,4) &= 3(6,1)+(6,2)+2(6,4),\\
(6,4)(6,1) &=2(6,1)+3(6,2)+(6,4).
\end{align*}
It follows
\begin{align*}
(6,1)(6,2)(6,4)&=(6,1)(3(6,1)+(6,2)+2(6,4))\\
&=3(6,1)^2 +(6,1)(6,2)+2(6,1)(6,4)\\
&=[12 - 3(6,2)] + [(6,1)+2(6,2)+3(6,4)] + 2[2(6,1)+3(6,2)+(6,4)]\\
&=12 +5(6,1) +5(6,2)+5(6,4)\\
&=7
\end{align*}
We have obtained
$$\eta_1+ \eta_2+\eta_3 = -1,\ \eta_1\eta_2+\eta_2\eta_3+\eta_3\eta_1 = -6,\  \eta_1 \eta_2 \eta_3 = 7.$$
Hence the minimal polynomial of $\eta_1$ over $\Q$ (and also of  $\eta_2,\eta_3$) is
$$f=(x-\eta_1)(x-\eta_2)(x-\eta_3) = x^3+x^2-6x-7.$$
The splitting field of $f$ is  $L_6=\Q(\eta_1)$ generated by the 6-periods.


\item[(e)]
We obtain the cosets $\lambda H_3$ with Sage:
\begin{verbatim}
b = Mod(2^6, 19)
ld = [sorted([2^j * b^i for i in range(3)]) for j in range(6)]; ld
[[1, 7, 11], [2, 3, 14], [4, 6, 9], [8, 12, 18], [5, 16, 17], [10, 13, 15]]
\end{verbatim}

Since
\begin{align*}
H_6 &= \{1,7,11\} \cup \{8,12,18\} = H_3 \cup 8 H_3,\\
2H_6 &=\{2,3,14\} \cup \{5,16,17\} = 2H_3 \cup 16H_3,\\
4H_6 &= \{4,6,9\} \cup \{10,13,15\} = 4H_3 \cup13H_3,
\end{align*}
we obtain
\begin{align*}
(6,1) &= (3,1) + (3,8),\\
(6,2) &= (3,2) + (3,16),\\
(6,4) &= (3,4) + (3,13).
\end{align*}
In Example 9.2.12, we have proved that the minimal polynomial of $(3,1)$ and $(3,8)$ over $L_6$ is
$$(x-(3,1))(x-(3,8)) = x^2 - (6,1)x + (6,4)+3 = x^2 - \eta_1 x + \eta_2 + 3.$$
If $\sigma  \in \Gal(\Q(\zeta_p)/\Q)$ is determined by $\sigma(\zeta_{19})= \zeta_{19}^2$ then $\sigma((3,1)) = (3,2),\sigma((3,8)) = (3,16) ,\sigma((6,1)) = (6,2),\sigma(6,4) = (6,8)=(6,1)$, so the minimal polynomial of $(3,2)$ is
$$(x-(3,2))(x-(3,16)) = x^2 - (6,2)x +(6,1)+3.$$
Similarly, applying $\sigma^2$, we obtain
$$(x-(3,4))(x-(3,13)) = x^2 - (6,4) x +(6,2)+3.$$


\item[(f)] The extension $L_1/L_3 = \Q(\zeta_{19})/\Q((3,1))$ is an extension of degree $d=3$. 

Here $[1]H_3 = \{[1],[7],[11]\} = [1]H_{1} \cup [7] H_{1} \cup [11] H_{1}$ (with $H_1=\{1\}$). Proposition 9.2.8 shows that the minimal polynomial of $\zeta_{19}$ over $L_3$ is
$$( x- (1,1))(x-(1,7))(x-(1,11)) = (x-\zeta_{19})(x-\zeta_{19}^7)(x- \zeta_{19}^{11}).$$
Without Proposition 9.2.8, note that $\Gal(L_1/L_3) = \tilde{H}_3 =  \langle \sigma^6 \rangle = \{e, \sigma^6, \sigma^{12}\}$, where $\sigma^6$ takes $\zeta_{19}$ to $\zeta_{19}^{2^6} = \zeta_{19}^7$, so the minimal polynomial of $\zeta_{19}$ over $L_3$ is
$$(x-\zeta_{19})(x-\sigma^6(\zeta_{19}))(x- \sigma^{12}(\zeta_{19})) = (x-\zeta_{19})(x-\zeta_{19}^7)(x- \zeta_{19}^{11}).$$
As 
\begin{align*}
\zeta_{19}+ \zeta_{19}^7+\zeta_{19}^{11} &= (3,1),\\
\zeta_{19} \zeta_{19}^7\zeta_{19}^{11} &= \zeta_{19}^{19} = 1,\\
\zeta_{19} \zeta_{19}^7+\zeta_{19}^7\zeta_{19}^{11}+\zeta_{19}\zeta_{19}^{11}  &= \zeta_{19}^8 + \zeta_{19}^{18}+ \zeta_{19}^{12} = (3,8),
\end{align*}
we obtain that the minimal polynomial of $\zeta_{19}$ over $L_3$ is
$$ (x-\zeta_{19})(x-\zeta_{19}^7)(x- \zeta_{19}^{11}) = x^3-(3,1)x^2+(3,8)x-1.$$

\end{enumerate}
\end{proof}

\paragraph{Ex. 9.2.8}

{\it In this exercise and the next, you will derive Gauss's radical formula (9.19) for $\cos(2\pi/17)$.
\be
\item[(a)] Show that $3$ is a primitive root modulo $17$.
\item[(b)] Show that
   \begin{align*}
   H_8 &= \{1,2,4,8,9,13,15,16\},\\
   H_4 &= \{1,4,13,16\},\\
   H_2 &= \{1,16\}.
   \end{align*}
   \item[(c)]Use Propositions 9.2.8 and 9.2.9 to compute the following minimal polynomials:
$$
\begin{array}{c|c|c}
 \mathrm{Extension} & \mathrm{Primitive}\  \mathrm{Elements}   &   \mathrm{Minimal}\  \mathrm{Polynomial} \\
 \hline
 \Q\subset L_8 & (8,1),(8,3)  &  x^2+x-4 \\
  \hline
 L_8\subset L_4 & (4,1),(4,2)  &  x^2 -(8,1)x-1  \\
 & (4,3),(4,6) & x^2-(8,3)x-1\\
   \hline
  L_4 \subset L_2& (2,1),(2,4) & x^2-(4,1)x+(4,3)
\end{array}
$$
The resulting quadratic equations are easy to solve using quadratic formula. But how do the roots correspond to the periods? For example, the roots $(8,1),(8,3)$ of $x^2+x-4$ are $(-1\pm\sqrt{17})/2$. How do these match up? The answer will be given in the next exercise.
\ee}

\begin{proof}
\begin{enumerate}
\item[(a)] By Exercise 1,
 $3^8 \equiv 9^4 =81^2\equiv(-4)^2 \equiv -1 \not \equiv 1 \pmod {17}$, therefore the order of $[3]$ in $(\Z/17\,\Z)^*$ is $16$, so 3 is a primitive root modulo $17$.

\item[(b)]
\begin{align*}
H_8 = \langle 3^2 \rangle &=\{1,9,9^2,9^3,-1,-9,-9^2,-9^3\} \\
&= \{1,9,-4,-2,-1,-9,4,2\}\\
&= \{1,9,13,15,16,8,4,2\},
\end{align*}
  $H_4 =\langle 3^4 \rangle= \{1,13,16,4\}$, and  $H_2 = \langle 3^8 \rangle = \{1,16\}$, so 
\begin{align*}
H_8 &= \{1,2,4,8,9,13,15,16\},\\
H_4 &= \{1,4,13,16\},\\
H_2 &= \{1,16\}.
\end{align*}

\item[(c)] 
\be
\item[$\bullet$] Extension $\Q \subset L_8$.

The cosets of $H_8$ in $(\Z/17\,\Z)^*$ are
\begin{align*}
H_8 &= \{1,2,4,8,9,13,15,16\},\\
3H_8 &=\{3, 6, 12, 7, 10, 5, 11, 14\}.
\end{align*}
(Verification Sage :
\begin{verbatim}
a = Mod(3,17)
lc = [sorted([a^j*a^(2*i) for i in range(8)]) for j in range(2)]; lc
[[1, 2, 4, 8, 9, 13, 15, 16], [3, 5, 6, 7, 10, 11, 12, 14]] )
\end{verbatim}
 $L_8$ is generated over $\Q$ by the 8-periods $(8,1),(8,3)$, where $(8,1) + (8,3) = -1$, and
\begin{align*}
(8,1)(8,3) &= \sum_{\lambda \in H_8} (8,\lambda+3)\\
&=(8,4)+(8,5)+(8,7)+(8,11)+(8,12)+(8,16)+(8,1)+(8,2)\\
&=4(8,1)+4(8,3)\\
&=-4.
\end{align*}
The minimal polynomial over $\Q$ of the 8-periods $(8,1),(8,3)$ is so
$$(x-(8,1))(x-(8,3)) = x^2 +x-4.$$

\item[$\bullet$] Extension $L_8 \subset L_4$.

\begin{align*} 
H_8 &= \{1,4,13,16\} \cup \{2,8,9,15\} = H_4 \cup 2 H_4,\\
3 H_8 &= \{3,5,12,14\} \cup \{6,7,10,11\} = 3H_4 \cup 6H_4.
\end{align*}
The 4-periods are so $(4,1),(4,2)$, and $(4,3),(4,6)$, where
\begin{align*}
(4,1) + (4,2) &= (8,1),\\
(4,1)\times(4,2) &= \sum_{\lambda \in H_4} (4,\lambda+2)\\
&= (4,3)+(4,7)+(4,15)+(4,1)\\
&=-1.
\end{align*}
The minimal polynomial of $(4,1)$ and $(4,2)$ over $L_8$ is so
$$(x-(4,1))(x-(4,2)) = x^2 -(8,1) x -1.$$
Applying $\sigma : \zeta_{17} \mapsto \zeta_{17}^3$, we obtain the minimal polynomial of $(4,3)$ and $(4,6)$ 
$$(x-(4,3))(x-(4,6)) = x^2 -(8,3) x -1.$$

\item[$\bullet$]  Extension $L_4\subset L_2$.
\begin{align*}
H_4 &= \{1,16\} \cup \{4,13\} = H_2 \cup 4 H_2,\\
3H_4 &=\{3,14\} \cup \{5,12\} = 3 H_2 \cup 5 H_2,\\
&\cdots
\end{align*}
The $2$-periods $(2,1),(2,4)$ satisfy
\begin{align*}
(2,1)+(2,4) &= (4,1),\\
(2,1)\times (2,4) &= \sum_{\lambda \in H_2}(2,\lambda + 4)\\
&=(2,5)+(2,3)\\
&=(4,3).
\end{align*}
The minimal polynomial of $(2,1)$ and $(2,4)$ over $L_4$ is so
$$(x-(2,1))(x-(2,4)) = x^2 - (4,1)x+(4,3).$$
\ee
\end{enumerate}
\end{proof}

\paragraph{Ex. 9.2.9}

{\it In this exercise, you will use numerical computations and the previous exercise to find radical expressions for various $f$-periods when $p=17$.
\be
\item[(a)] Show that
\begin{align*}
(8,1) &=  2\cos(2\pi/17) + 2\cos(4\pi/17)+2\cos(8\pi/17)+2\cos(16\pi/17)\\
(4,1) &= 2\cos(2\pi/17)+2\cos(8\pi/17)\\
(4,3) &= 2\cos(6\pi/17)+2\cos(10\pi/17)\\
(2,1) &= 2\cos(2\pi/17)
\end{align*}
Then compute each of these periods to five decimal places.
\item[(b)] Use the numerical computations of part (a) and the quadratic polynomials of Exercise 8 to show that
\begin{align*}
(8,1) &= \frac{1}{2}\left(-1+\sqrt{17}\right)\\
(8,3) &= \frac{1}{2}\left(-1-\sqrt{17}\right)\\
(4,1) &= \frac{1}{4} \left(-1+\sqrt{17} +\sqrt{34-2\sqrt{17}}\right)\\
(4,2) &= \frac{1}{4} \left(-1+\sqrt{17} - \sqrt{34-2\sqrt{17}}\right)\\
(4,3) &= \frac{1}{4} \left(-1-\sqrt{17} +\sqrt{34+2\sqrt{17}}\right)
\end{align*}

\item[(c)] Use the quadratic polynomial $x^2 - (4,1) x + (4,3)$ and part (b) to derive (9.19).
\ee
}

\begin{proof}
Recall (see Exercise 8) that
\begin{align*}
H_8 &= \{1,2,4,8,9,13,15,16\}\\
H_4 &= \{1,4,13,16\}\\
3H_4 &= \{3,5,12,14\}\\
H_2 &= \{1,16\}
\end{align*}
Write $\zeta=\zeta_{17}$.

\begin{enumerate}
\item[(a)]
Using these results, and $\zeta^{-k} = \zeta^{17-k}, k=1,2,4,8$, and also $\zeta^{k} + \zeta^{-k} = 2 \cos(2k\pi/17)$, we obtain
\begin{align*}
(8,1) &= \sum_{[a]\in H_8} \zeta^a\\
&=\zeta+ \zeta^2 + \zeta^4 + \zeta^8+\zeta^9 + \zeta^{13}+ \zeta^{15}+\zeta^{16}\\
&=(\zeta+\zeta^{-1})+ (\zeta^2+\zeta^{-2})+(\zeta^4+\zeta^{-4})+ (\zeta^8+\zeta^{-8})\\
&= 2\cos(2\pi/17) + 2\cos(4\pi/17)+2\cos(8\pi/17)+2\cos(16\pi/17)\\
\\
(4,1) &= \sum_{[a]\in H_4} \zeta^a\\
&=\zeta+\zeta^4+\zeta^{13}+ \zeta^{16}\\
&= (\zeta+ \zeta^{-1}) + (\zeta^4+\zeta^{-4})\\
&= 2\cos(2\pi/17)+2\cos(8\pi/17)
\\
(4,3) &=  \sum_{[a]\in 3H_4} \zeta^a\\
&=\zeta^{3}+\zeta^5+\zeta^{12}+ \zeta^{14}\\
&= (\zeta^{3}+ \zeta^{-3}) + (\zeta^5+\zeta^{-5})\\
&= 2\cos(6\pi/17)+2\cos(10\pi/17)\\
\\
(2,1) &= \sum_{[a]\in H_2} \zeta^a\\
&=\zeta+\zeta^{16}\\
&=\zeta+ \zeta^{-1}\\
&=2\cos(2\pi/17)
\end{align*}
$(2,1) = 2\cos(2\pi/17) \simeq 0.93247$,

$(4,1) \simeq 2.04948, (4,3)\simeq 0.34415$, 

$(8,1) \simeq 1.56155$.

As $(4,1)+(4,2) = (8,1)$, we obtain $(4,2) \simeq -0.48792<0$.

\item[(b)]
By Exercise 8, $(8,1),(8,3)$ are the roots of $x^2+x-4$, and by part (a) $(8,1)>0$. The only positive root of $x^2+x-4$ is $(-1+\sqrt{17})/2$, therefore
\begin{align*}
(8,1) &= \frac{1}{2}\left(-1+\sqrt{17}\right),\\
(8,3) &= \frac{1}{2}\left(-1-\sqrt{17}\right).\\
\end{align*}
$(4,1),(4,2)$ are the roots of $x^2-(8,1)x-1$, with discriminant $$\Delta= \frac{1}{4}(-1+\sqrt{17})^2+4 = \frac{1}{4}(34 - 2\sqrt{17}),$$ therefore
$$\{(4,1),(4,2)\} =\left \{\frac{1}{4} \left(-1+\sqrt{17} +\sqrt{34-2\sqrt{17}}\right), \frac{1}{4} \left(-1+\sqrt{17} -\sqrt{34-2\sqrt{17}}\right)\right\}.$$
By part (a) $(4,2)<0<(4,1)$, so
\begin{align*}
(4,1) &= \frac{1}{4} \left(-1+\sqrt{17} +\sqrt{34-2\sqrt{17}}\right),\\
(4,2)&= \frac{1}{4} \left(-1+\sqrt{17} - \sqrt{34-2\sqrt{17}}\right).
\end{align*}
$(4,3),(4,6)$ are the roots of $x^2-(8,3)x-1$, with discriminant $$\Delta= \frac{1}{4}(-1-\sqrt{17})^2+4 = \frac{1}{4}(34 + 2\sqrt{17}),$$ therefore
$$\{(4,3),(4,6)\} =\left \{\frac{1}{4} \left(-1-\sqrt{17} +\sqrt{34+2\sqrt{17}}\right), \frac{1}{4} \left(-1-\sqrt{17} -\sqrt{34+2\sqrt{17}}\right)\right\}.$$
As $(4,3)>0$,
\begin{align*}
(4,3) &= \frac{1}{4} \left(-1-\sqrt{17} +\sqrt{34+2\sqrt{17}}\right),\\
(4,6) &=\frac{1}{4} \left(-1-\sqrt{17} -\sqrt{34+2\sqrt{17}}\right).
\end{align*}


\item[(c)]
$(2,1) = 2\cos(2\pi/17)$, and also $(2,4)$, is root of $x^2 -(4,1)x+(4,3)$, with discriminant $$\Delta = (4,1)^2 - 4(4,3).$$
As
\begin{align*}
(4,1)^2 &= \sum\limits_{\lambda \in H_4} (4,\lambda+1)\\
&=(4,2)+(4,5)+(4,14)+4\\
&=(4,2)+2(4,3)+ 4,
\end{align*}
then 
\begin{align*}
\Delta &= (4,2) -2(4,3) + 4\\
&= \frac{1}{4} \left (  -1+\sqrt{17}- \sqrt{34-2\sqrt{17}} -2\left(-1-\sqrt{17} +\sqrt{34+2\sqrt{17}}\right) +16\right)\\
&= \frac{1}{4} \left ( 17 + 3\sqrt{17} - \sqrt{34-2\sqrt{17}}  -2 \sqrt{34+2\sqrt{17}} \right).
\end{align*}
The roots of $x^2 -(4,1)x+(4,3)$ are so
$\frac{1}{2}((4,1)\pm \sqrt{\Delta})$

$=\frac{1}{8} \left(-1+\sqrt{17} +\sqrt{34-2\sqrt{17}}\right) \pm \frac{1}{4} \sqrt{17 + 3\sqrt{17} - \sqrt{34-2\sqrt{17}}  -2 \sqrt{34+2\sqrt{17}} }.$

As $(2,4) = 2\cos(8\pi/17) < 2 \cos(2\pi/17) = (2,1)$, we can conclude that

 \begin{align*}
\cos\left(\frac{2\pi}{17}\right) =&-\frac{1}{16}+ \frac{1}{16}\sqrt{17} +\frac{1}{16}\sqrt{34-2\sqrt{17}}\\
 & + \frac{1}{8} \sqrt{17 + 3\sqrt{17} - \sqrt{34-2\sqrt{17}}  -2 \sqrt{34+2\sqrt{17}} }.
 \end{align*}
 
\end{enumerate}
\end{proof}

\paragraph{Ex. 9.2.10}

{\it Let $p=11$. Prove that $y^5+y^4-4y^3-3y^2+3y+1$ is the minimal polynomial of the $2$-period $(2,1)=2\cos(2\pi/11)$.
}

\begin{proof}
Let $\zeta = \zeta_{11} = e^{2i\pi/11}$, and $\eta = (2,1) = \zeta + \zeta^{-1} = 2 \cos(2\pi/11)$. 
The powers of 2 modulo 11 are $1,2,2^2=4,2^3 =8, 2^4=5,2^5=-1$, so the order of $[2]$ in $(\Z/11\, \Z)^*$ is 10, so 2 is a primitive root modulo 11.

As $\Phi_{11}(\zeta) = 1+\zeta+\zeta^{2}+\zeta^{3}+\zeta^{4}+\zeta^{5}+\zeta^{6}+\zeta^{7}+\zeta^{8}+\zeta^{9}+\zeta^{10}=0$, we obtain by multiplication by $\zeta^{-5}$ :
\begin{align}
(\zeta^{-5} + \zeta^5)+(\zeta^{-4} + \zeta^4)+(\zeta^{-3} + \zeta^3)+(\zeta^{-2} + \zeta^2)+(\zeta^{-1} + \zeta) + 1=0. \label{eq:1}
\end{align}
Write $u_n = \zeta^n+\zeta^{-n}$. As 
\begin{align*}
\zeta^{n+2} + \zeta^{-n-2} = (\zeta+\zeta^{-1})(\zeta^{n+1}+\zeta^{-n-1}) - (\zeta^n+\zeta^{-n}),
\end{align*}
we obtain for all $n\in \N$
$$u_{n+2} = \eta \,u_{n+1} - u_n, \ u_0 = 2,u_1 = \eta.$$
Therefore
\begin{align*}
\zeta+\zeta^{-1} &= \eta,\\
\zeta^2+\zeta^{-2} &= \eta^2-2,\\
\zeta^3+\zeta^{-3} &=\eta(\eta^2-2)-\eta = \eta^3-3\eta,\\
\zeta^4+\zeta^{-4} &=\eta(\eta^3-3\eta) - (\eta^2-2) = \eta^4-4\eta^2+2,\\
\zeta^5+\zeta^{-5} &=\eta(\eta^4-4\eta^2+2)-(\eta^3-3\eta) = \eta^5-5\eta^3+5\eta.
\end{align*}
The equality \eqref{eq:1} gives
\begin{align*}
0 &= (\eta^5-5\eta^3+5\eta)+(\eta^4-4\eta^2+2)+(\eta^3-3\eta)+(\eta^2-2)+\eta+1\\
&=\eta^5+\eta^4-4\eta^3 - 3 \eta^2+3\eta + 1.
\end{align*}
So $\eta$ is a root of $f= x^5+x^4-4x^3-3x^2+3x+1 \in \Q[x]$.

By Proposition 9.2.6 (b), the fixed field $L_2$ of $\tilde{H}_2$ corresponding to $H_2 = \{-1,1\}$ is $L_2 = \Q(\eta)$, and $[L_2:\Q] = 5$ by Proposition 9.2.1.
(as $\Q \subset \Q(\zeta)$ is a Galois extension, $[\Q(\eta):\Q] =\vert \Gal(\Q(\eta)/\Q) \vert=  (G:\tilde{H}_2) =((\Z/11\Z)^* : \{-1,1\}) = 5$).

The minimal polynomial $g$ of $\eta$ over $\Q$ divides $f$, and has degree 5, so $g = f$.

Using the other form of the minimal polynomial given in Proposition 9.2.6(a), we obtain that
\begin{align*}
&(x-\zeta-\zeta^{-1})(x-\zeta^{2}-\zeta^{-2})(x-\zeta^{3}-\zeta^{-3})(x-\zeta^{4}-\zeta^{-4})(x-\zeta^{5}-\zeta^{-5}) \\
&=x^5+x^4-4x^3-3x^2+3x+1
\end{align*}
is the minimal polynomial of $\eta = \zeta_{11}+ \zeta_{11}^{-1}$ over $\Q$.
\end{proof}

\paragraph{Ex. 9.2.11}

{\it Let $L_{fq} \subset L_f$ be the extension studied in Theorem 9.2.14. Thus $f$ and $fq$ divide $p-1$, and $q$ is prime. As usual, $ef=p-1$ and $g$ is a primitive root modulo $p$. Finally, let $\omega$ be a primitive $q$th root of unity.
\be
\item[(a)] Let $\tau \in \Gal(\Q(\zeta_p)/\Q)$ satisfy $\tau(\zeta_p) = \zeta_p^{g^{e/q}}$, and let $\sigma' = \tau|_{L_f}$ be the restriction of $\tau$ to $L_f$. Prove that $\sigma'$ generates $\Gal(L_f/L_{fq})$.
\item[(b)] Prove that $\Gal(L_f(\omega)/L_{fq}(\omega))\simeq \Gal(L_f/L_{fq})$, where the isomorphism is defined by restriction to $L_f$.
\item[(c)] Let $\sigma \in \Gal(L_f(\omega)/L_{fq}(\omega))$ map to the element $\sigma' \in \Gal(L_f/L_{fq})$ constructed in part (a). Prove that $\sigma$ satisfies (9.21).
\item[(d)] Prove the coset decomposition of $H_{fq}$ given in (9.23).
\ee
}

\begin{proof}
\begin{enumerate}
\item[(a)]
Let $f' = fq$, and $e'=n/f'$. Then $p-1 = ef = e'f'$, and $e = e'q$.

By section 9.2, 
\begin{center}
$L_f$ is the fixed field of $\tilde{H}_f = \langle \sigma \rangle$, where $\sigma(\zeta_p ) = \zeta_p^{g^e}$.
\end{center}
$\tilde{H}_f$ is the set of automorphisms $\xi$ such that $\zeta_p \mapsto \xi(\zeta_p) =  \zeta_p^i,\   i \in H_f = \{1,g^e,g^{2e},\cdots,g^{(f-1)e}\}$.

This result applied to $f'$ gives:
\begin{center}
$L_{fq}$ is the fixed field of $\tilde{H}_{fq}= \langle \tau \rangle$, where  $\tau(\zeta_p ) = \zeta_p^{g^{e'}} = \zeta_p^{g^{e/q}}$.
\end{center}
By the Galois correspondence,  $\Gal(\Q(\zeta_p)/L_{fq}) =\tilde{H}_{fq} = \langle \tau \rangle$.

As $\Q \subset L_f$ is a Galois extension, $\tau L_f = L_f$ (Theorem 7.2.5).

 If $\sigma' : L_f \to L_f$ is the restriction of $\tau$ to  $L_f$, then $\sigma' \in \Gal(L_f/L_{fq})$.

The restriction mapping $\psi : \Gal(\Q(\zeta_p)/L_{fq}) \to \Gal(L_f/L_{fq})$ is a surjective mapping by the proof of Theorem 7.2.7, so every element of  $\Gal(L_f/L_{fq})$ is of the form $\psi(\tau^k) = \sigma'^k,\ k \in \Z$, therefore
$$\Gal(L_f/L_{fq}) = \langle \sigma' \rangle.$$

Since $\vert \Gal(L_f/L_{fq}) \vert = q$ (Proposition 9.2.1), the order of $\sigma'$ is $q$.

Note: as $\tau(\zeta_p )  = \zeta_p^{g^{e/q}}, \tau((f,\lambda)) = (f,g^{e/q} \lambda)$, for every period $(f,\lambda)$ (Lemma 9.2.4(d)), and $(f,\lambda) \in L_f$, so
$$\sigma'((f,\lambda)) = (f,g^{e/q} \lambda).$$


\item[(b)]

Since $q\mid p-1, p\wedge q = 1$, therefore $\Phi_q(x) = \frac{x^{q}-1}{x-1}$ is irreducible over $\Q(\zeta_p)$ by Exercise 9.1.16. Hence $\Phi_q$ is a fortiori irreducible over the subfields $L_f,L_{fq}$ of $\Q(\zeta_p)$.
Consequently $$[L_f(\omega):L_f] = [L_{fq}(\omega) : L_{fq}] = \deg(\Phi_q) =  q-1.$$
 
 $L_f(\omega)$ is the splitting field of $\Phi_q$ over $L_f$, $L_f \subset L_f(\omega)$ is thus a Galois extension, and similarly $L_{fq} \subset L_{fq}(\omega)$ is Galois.
 
By Exercises 8.3.2 and 8.2.7, $L_f(\omega)$ is a Galois extension of $L_{fq}$, a fortiori of $L_{fq}(\omega)$.

Let 
$$
\varphi : 
\left\{
\begin{array}{ccc}
 \Gal(L_f(\omega)/L_{fq}(\omega)) & \to   & \Gal(L_f/L_{fq})  \\
  \sigma &  \mapsto &  \sigma \vert_{L_f}
\end{array}
\right.
$$
This mapping is well defined since $L_f$ is a normal extension of $L_{fq}$, so $\sigma L_f =L_f$, and $\sigma$ fixes the elements of $L_{fq}(\omega)$, a fortiori the elements of $L_{fq}$.

$\varphi$ is a group homomorphism, and $\varphi$ is injective: 

if $\sigma \in \ker(\varphi)$, then $\sigma(\omega) = \omega$, and $\sigma$ is the identity on $L_f$, thus $\sigma$ is the identity on $L_f(\omega)$, so $\sigma = e$, therefore $\ker(\varphi) = \{e\}$.

Moreover, $[L_f:L_{fq}] = q$ and $[L_f(\omega):L_f] = [L_{fq}(\omega) : L_{fq}] = q-1$, therefore, by the Tower Theorem, $[L_f(\omega):L_{fq}(\omega)] = q$.
Hence $\vert  \Gal(L_f(\omega)/L_{fq}(\omega)) \vert = \vert \Gal(L_f,L_{fq}) \vert = q$, so $\varphi$ is a group isomorphism.

\item[(c)] Let $\sigma = \varphi^{-1}(\sigma')$. Then $\sigma$ is a generator of $\Gal(L_f(\omega)/L_{fq}(\omega))$, and $\varphi(\sigma) = \sigma'$.

As $\sigma\vert _{L_f} = \sigma'$, by the note in part (a),
$$\sigma((f,\lambda)) =  \sigma'((f,\lambda)) = (f,g^{e/q} \lambda).$$


\item[(d)] $H_f = \langle g^e \rangle$, and $H_{fq} = \langle g^{e/q} \rangle$.

We show first that $g^{k(e/q)} \not \in H_f$ if $1 \leq k \leq  q-1$. If not, there would exist an integer $j$ such that $g^{k(e/q)} = g^{je}$. As the order of $g$ is $p-1=ef$, $ef \mid k \frac{e}{q} - je$, so $\lambda e f q = ke -jeq ,\lambda \in \Z$, therefore $\lambda f q = k -jq$, and so $q \mid k$. It is impossible since $1 \leq k \leq  q-1$.

If $0 \leq i < j \leq q-1$, by the preceding result, $(g^{i(e/q)})^{-1} g^{j(e/q)} = g^{(j-i)(e/q)}  \not \in H_f$, therefore  $g^{i(e/q)} H_f \neq g^{j(e/q)}H_f$.

The $q$ left cosets $H_f,g^{e/q} H_f,g^{2e/q} H_f,\cdots,g^{(q-1)e/q} H_f$ are so distinct. Since $(H_{fq} : H_f) = q$, the set of left cosets is reduced to these $q$ cosets, which give a partition of $H_{fq}$:
$$H_{fq} = H_f \cup g^{e/q} H_f \cup g^{2e/q} H_f \cup \cdots \cup g^{(q-1)e/q} H_f.$$
\end{enumerate}
\end{proof}

\paragraph{Ex. 9.2.12}

{\it Let $p$ be an odd prime, and let $m$ be a positive integer relatively prime to $p$.
\be
\item[(a)] Prove that $1,\zeta_p,\ldots,\zeta_p^{p-2}$ are linearly independent over $\Q(\zeta_m)$.
\item[(b)] Explain why part (a) implies that $\zeta_p,\ldots,\zeta_p^{p-1}$ are linearly independent over $\Q(\zeta_m)$.
\item[(c)] Let $f \mid p-1$. Prove that the $f$-periods are linearly independent over $\Q(\zeta_m)$.
\ee
}

\begin{proof}
\begin{enumerate}
\item[(a)]
As $p\wedge m = 1$, $\Phi_p(x) = x^{p-1}+\cdots+x+1$ is irreducible over $\Q(\zeta_m)$ by Exercise 9.1.16.
Therefore the minimal polynomial of $\zeta_p$ over $\Q(\zeta_m)$ is $\Phi_p(x)$, of degree $p-1$, so $1,\zeta_p,\zeta_p^2,\cdots,\zeta_p^{p-2}$ are linearly independent over $\Q(\zeta_m)$.

\item[(b)]If $a_1,\cdots,a_{p-1} \in \Q(\zeta_m)$, as $\zeta_p\neq 0$,
$$a_1\zeta_p + a_2\zeta_p^2+\cdots+a_{p-1} \zeta_p^{p-1} = 0 \Rightarrow a_1 + a_2\zeta_p+\cdots+a_{p-1} \zeta_p^{p-1} = 0 \Rightarrow a_1=a_2=\cdots=a_{p-1} = 0,$$
so $\zeta_p,\zeta_p^2,\cdots,\zeta_p^{p-1}$ are linearly independent over $\Q(\zeta_m)$.

\item[(c)] Suppose that $\sum\limits_{i=1}^{e} a_i (f,\lambda_i) = 0$, where $a_i \in \Q(\zeta_m)$. Let $\{[\lambda_1],\cdots,[\lambda_{e}]\}$ be a complete system of representatives of the cosets $[\lambda] H_f$, then
$$\sum_{i=1}^{e} a_i \sum_{a \in [\lambda_i] H_f}  \zeta_p^a = 0.$$
As $(\lambda_i H_f)_{1\leq i \leq e}$ is a partition of $(\Z/p\Z)^*$, this equality is equivalent to 
$$\sum_{[k] \in (\Z/p\Z)^*} b_k \zeta_p^k = \sum_{k=0}^{p-1} b_k \zeta_p^k=  0,$$
where $b_k$ is a constant on every coset  $[\lambda_i]H_f$, equal to $a_i$. 

Since $\zeta_p,\zeta_p^2,\cdots,\zeta_p^{p-1}$ are linearly independent over $\Q(\zeta_m)$, all the $b_k$ are zero, so  $a_1 = \cdots = a_e = 0$.

Thus $f$-periods are linearly independent over $\Q(\zeta_m)$.
\end{enumerate}
\end{proof}

\paragraph{Ex. 9.2.13}

{\it Prove (9.24):
$$\sum_{a=0}^{17} \legendre{a}{17} \zeta_{17}^a = \sqrt{17}.$$
}

\begin{proof}
By Exercise 8 (b), we have proved for $p=17$, that
\begin{align*}
(8,1) &= \frac{1}{2}\left(-1+\sqrt{17}\right),\\
(8,3) &= \frac{1}{2}\left(-1-\sqrt{17}\right).\\
\end{align*}
So
$$\sqrt{17} = (8,1)-(8,3) = \sum_{a \in H_8} \zeta^a - \sum_{a \in 3H_8} \zeta^a.$$

Let
$$\varphi : 
\left\{
\begin{array}{ccc}
 (\Z/p\Z)^* &  \to & (\Z/p\Z)^*  \\
 x & \mapsto  &  x^2.
\end{array}
\right.
$$
$\varphi$ is a group homomorphism.

As $x^2 = 1 \iff (x-1)(x+1) = 0 \iff x \in\{-1,1\}$, $\ker(\varphi) = \{-1,1\} \subset (\Z/p\Z)^*$. Write $C =\mathrm{im}(\varphi)$ the set of square elements in $(\Z/p\Z)^*$. Then $\mathrm{im}(\varphi) \simeq (\Z/p\Z)^*/\ker(\varphi)$, so
$|C| = |\mathrm{im}(\varphi) | = (p-1)/2 = 8$.
Moreover $H_8 = \langle 3^2 \rangle $ (Exercise 1), so $H_8 \subset C$, and $|H_8 | = 8 = |C|$, therefore $H_8 = C$ is the set of squares in $(\Z/17\, \Z)^*$.  Its complement $3H_8$ is the set of non squares in $(\Z/17\Z)^*$.

 Therefore, for all $a \in (\Z/17\Z)^*$. 
$$\legendre{a}{17} = 1 \iff a \in H_8,$$ $$ \legendre{a}{17} = -1 \iff a \in 3H_8,$$
and $\legendre{a}{17}=0$ if $a=0$ or $a=17$ (where we write for all integer $k$, $\legendre{[k]}{17} = \legendre{k}{17})$. Hence
$$\sum_{a=0}^{17} \legendre{a}{17} \zeta_{17}^a = \sqrt{17}.$$
\end{proof}

\paragraph{Ex. 9.2.14}

{\it Consider the quotation from Galois given at the end of the Historical Notes.
\be
\item[(a)] Show that the permutations obtained by mapping the first line in the displayed table to the other lines give a cyclic group of order $n-1$. Also explain how these permutations relate to the Galois group.
\item[(b)] Explain what Galois is saying in the last sentence of the quotation.
\ee
}

\begin{proof}
This group of permutations is generated by the cycle $$(a,b,c,\cdots,k) = (r,r^g,r^{g^2}, \cdots,r^{g^{n-2}}).$$ It is a cyclic subgroup of order $n-1$ in the group of permutation of the $n-1$ roots of $\Phi_n(x)$. The Galois group of $\Phi_n(x)$, as a permutation group of the roots, is indeed a cyclic group of order $n-1$, if $n$ is prime: 
$$\Gal_{\Q}(\Phi_n) = \Gal(\Q(\zeta_n)/\Q) \simeq (\Z/n\Z)^* \simeq C_{n-1}.$$
For such a Galois extension,
$$\vert \Gal(\Q(\zeta_n)/\Q) \vert = [\Q(\zeta_n):\Q] = n-1 = \deg(\Phi_n(x)).$$

\item[(b)] If all the roots are rational function of one fixed root $\alpha$ of $f$, then the extension $\Q \subset \Q(\alpha)$ is Galois, so  the equality $\vert \Gal(\Q(\alpha)/\Q) \vert = [\Q(\alpha) : \Q]  = \deg(f)$ is true for the minimal polynomial $f$ of $\alpha$ over $\Q$.
\end{proof}

\paragraph{Ex. 9.2.15}

{\it What are the 1-periods?
}

\begin{proof}
$H_1 = \{[1]\}$, and the coset of $[a] \in (\Z/p\Z)^*$ is $[a]H_{1} = \{[a]\}$, so  the 1-periods $(1,a)$ are the powers of $\zeta_p$: $$(1,a) = \zeta_p^a.$$
\end{proof}

\paragraph{Ex. 9.2.16}

{\it Redo Exercise 3 using periods.
}

\begin{proof}
If $p=7$, and $\zeta = e^{2i\pi/7}$, the 2-periods corresponding to $H_2 = \{-1,1\} = \{1,6\}$ are $(2,1) = \zeta + \zeta^{-1}, (2,2) = \zeta^2+\zeta^{-2}, (2,3) = \zeta^3+\zeta^{-3}$. By Proposition 9.2.6, they are the roots of the irreducible polynomial
$$f = (x- (2,1))(x-(2,2))(x-(2,3))$$
\begin{align*}
&(2,1)+(2,2)+(2,3)= -1,\\
&(2,1)^2 =\sum_{\lambda\in H_2} (2,\lambda+1) = (2,2)+2,\\
&(2,1)(2,2) =  \sum_{\lambda\in H_2} (2,\lambda+2) = (2,3)+(2,1).
\end{align*}
$3$ is a primitive root modulo 7. Let $\sigma$ the $\Q$-automorphism determined by $\sigma(\zeta) = \zeta^3$. Then $\sigma$ gives the chain $(2,1) \mapsto (2,3) \mapsto (2,2) \mapsto (2,1)$, so
$$(2,1)(2,2) =  (2,3)+(2,1),\quad (2,3)(2,1) =  (2,2)+(2,3), \quad (2,2)(2,3) = (2,1)+(2,2).$$

By summation of these equalities, 
$$(2,1)(2,2)+ (2,3)(2,1)+(2,2)(2,3) = 2(2,3) +2(2,1)+2(2,2) = -2.$$
Finally $$(2,1)(2,2)(2,3) = (2,1)[(2,1)+(2,2)] = (2,1)^2 + (2,1)(2,2) = (2,2)+ 2 +(2,3)+(2,1) = 1.$$

Therefore
$f = x^3 +x^2-2x-1$ is the minimal polynomial of $(2,1) = 2 \cos(2\pi/7)$ over $\Q$ (and also of $(2,2),(2,3)$).

The fixed field $L_2$ of $\tilde{H}_2$ corresponding to $H_2$ is $\Q(\zeta+\zeta^{-1})$, of degree 3 over $\Q$, and $\tilde{H}_2 = \{e,\tau\}$, where $\tau(\zeta) = \zeta^{-1} = \overline{\zeta}$, so $\tau$ is the restriction of the complex conjugation to $L_2$. The end of the proof is the same as in Exercise 3.
\end{proof}

\paragraph{Ex. 9.2.17}

{\it Let $f$ be an even divisor of $p-1$ where $p$ is an odd prime. Prove that every $f$-period $(f,\lambda)$ lies in $\R$.
}

\begin{proof}
As $2 \mid f$ is even, $H_2\subset H_f$ (Exercise 1), so every coset $[\lambda] H_f$ is a disjoint union of $[\mu] H_2$ (Exercise 4), so $$[\lambda] H_f = \bigcup_{[\mu] \in A} [\mu] H_2.$$
Therefore
$$(f,\lambda) = \sum_{a \in[\lambda] H_f} \zeta_p^a = \sum _{\mu \in A} \sum_{a \in [\mu] H_2} \zeta_p^{a} =\sum _{\mu \in A} (\zeta_p^{\mu} + \zeta_p^{-\mu}) \in \R. $$
\end{proof}

\end{document}