Exercise 11.2.14

Question

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

ewcommand{\be} {\begin{enumerate}}

ewcommand{\ee} {\end{enumerate}}

ewcommand{\deb}{\begin{eqnarray*}}

ewcommand{\fin}{\end{eqnarray*}}

ewcommand{\ssi} {si et seulement si }

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{\U}{\mathbb{U}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\im}{\,\mathrm{Im}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{\Gal}{\mathrm{Gal}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

In this exercise we will count the number of primitive elements of the extension $\F_p\subset \F_{p^n}$. This is the number
$$P_n = {\big |} \{\alpha \in \F_{p^n}\ | \ \F_{p^n} = \F_p(\alpha)\}{\big |}.$$
\be
\item[(a)] Use Corollary 11.1.8 to prove that $p^n = \sum_{m \mid n} P_m$.
\item[(b)] Use the M"obius inversion formula to conclude that $P_n = \sum_{m \mid n} \mu(m) p^{\frac{n}{m}}$. This formula was first proved by Dedekind in 1857.
\item[(c)] Explain how the formula of part (b) relates to Theorem 11.2.4.
\ee

Richard Ganaye · Accepted Answer

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

ewcommand{\be} {\begin{enumerate}}

ewcommand{\ee} {\end{enumerate}}

ewcommand{\deb}{\begin{eqnarray*}}

ewcommand{\fin}{\end{eqnarray*}}

ewcommand{\ssi} {si et seulement si }

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{\U}{\mathbb{U}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\im}{\,\mathrm{Im}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{\Gal}{\mathrm{Gal}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof}
\be
\item[(a)] Let $n\geq 1$ an integer. For every $k$ such that $k \mid n$, there exists a unique subfield of $\F_{p^n}$ with cardinality $p^k$, written $\F_{p^k}$, and no such subfield if $k
mid n$ (Corollary 11.1.8).

If $\alpha \in \F_{p^n}$, $\F_p(\alpha)$ is a subfield of $\F_{p^n}$, so $\F_p(\alpha) = \F_{p^m}$ for some $m$, with $m\mid n$. Therefore
$$\F_{p^n} = \coprod_{m\mid n}\ \{\alpha \in \F_{p^n} \ |\ \F_p(\alpha) = \F_{p^m}\}.  $$
As $\F_p(\alpha) =  \F_{p^m}$ implies that $\alpha \in \F_{p^m}$,
$$\{\alpha \in \F_{p^n} \ |\ \F_p(\alpha) = \F_{p^m}\} = \{\alpha \in \F_{p^m} \ |\ \F_p(\alpha) = \F_{p^m}\},$$
therefore 
$$ {\big |} \{\alpha \in \F_{p^n} \ |\ \F_p(\alpha) = \F_{p^m}\}{\big |} = P_m.$$
Consequently,
$$p^n = {\big |} \F_{p^n}{\big |} = \sum_{m\mid n} {\big |}  \{\alpha \in \F_{p^n} \ |\ \F_p(\alpha) = \F_{p^m}\} {\big |} = \sum_{m \mid n} P_m.$$
\ee

\item[(b)] If we write $G(n) = p^n$ and $F(n) = P_n$ as in the proof of Theorem 11.2.4, then
$$G(n) = \sum_{m\mid n} F(n).$$
By the M"obius inversion formula,
$$F(n) = \sum_{m\mid n} \mu(m) G\left(\frac{n}{m}ight),$$
so, for all positive integer $n$,
$$P_n = \sum_{m \mid n} \mu(m) p^{\frac{n}{m}}.$$

\item[(c)] Let $\alpha$ be a primitive element of $\F_{p^n}$, and $f$ the minimal polynomial of $\alpha$ over $\F_p$. Then $\deg(f) = [\F_{p^n} : \F_p] = n$. Since the extension $\F_p \subset \F_{p^n}$ is normal, $f$ splits completely in $\F_{p^n}$, so there exist exactly $n$ primitive elements in $\F_{p^n}$ with the same minimal polynomial. Moreover two distinct monic irreducible polynomials have no common root.

If we write $A_n = \{\alpha \in \F_{p^n}\ | \ \F_{p^n} = \F_p(\alpha)\}$ the set of primitive elements of the extension $\F_p\subset \F_{p^n}$, and ${\mathcal N}_n$ the set of monic irreducible polynomials $f \in \F_p[x]$ of degree $n$, then by definition $|A_n| = P_n$ and $|{\mathcal N}_n| =N_n$. The map $\varphi : A_n 	o {\mathcal N}_n$ defined by $\alpha \mapsto \mathrm{Irr}(\alpha,\F_p)$, where $\mathrm{Irr}(\alpha,\F_p)$ is the minimal polynomial of $\alpha$ over $\F_p$ is onto, and is such that every element of ${\mathcal N}_n$ has $n$ preimages, with $\varphi^{-1}(f) \cap \varphi^{-1}(g) = \emptyset$ if $f, g \in {\mathcal N_n}, f 
e g$, thus $|A_n| = n |\mathcal N_n|$:
$$P_n = n N_n.$$
We find a new proof of the Theorem 11.2.4:
$$N_n = \frac{1}{n} \sum_{m \mid n} \mu(m) p^{\frac{n}{m}}.$$
Conversely, if we know Theorem 11.2.4, we find the formula of part (b): these two formulas are equivalent.
\end{proof}

Exercise 11.2.14

Answers

Comments

Exercise 11.2.14

Answers

Comments

Add answer