# Generators of Finite Fields and Quadratic Extensions

I want to show that if an element in $\beta \in K$ where $|K|=p^n$ is a generator for $K^*$, i.e. has order $p^n-1$, then there is a generator $\alpha\in L$, $[L,K]=2$ i.e. of order $(p^n)^2-1$, such that $\alpha^{p^n+1}=\beta$.

I've tried rephrasing the question to understand it in a different way, but it hasn't helped. Essentially the question is the same as: Show that there is a root to $x^{q+1}-\beta$ in $L$ such that it is a generator of $L^*$ given that $\beta$ is a generator of $K^*$.

Initial thoughts: In a previous question, I now understand that every $\beta\in K$ can be written as $\alpha^{q+1}$ for some $\alpha\in L$ but it is not obvious that if $\beta$ is a $K^*$ generator, then the element $\alpha\in L$ that satisfies $\alpha^{q+1}=\beta$ necessarily is a generator for $L^*$. The converse is obvious, if $\alpha$ is a generator of $L^*$ then $\alpha^{q+1}$ is clearly in $K$ and is a generator because the lowest power that takes $\alpha$ to the identity is $q^2-1$ so we have to raise $\alpha^{q+1}$ to the power $q-1$ to do that, which means it is a generator for $K^*$. But the direction I want has been more difficult for me, because for a given generator of $K^*$, say $\beta$, then an element $\alpha\in L$ of order $q-1$ could work, because we obviously have $\alpha^{q+1}\in K^*$ and the lowest common multiple of $(q+1,q-1)=(q^2-1)/\delta$ where $\delta=1$ if $q=2^n$ and $\delta=2$ otherwise. Not sure where to go from here.

-
Essentially the question is about a surjective homomorphism from one finite cyclic group to another. Therefore I took the liberty of adding a couple of tags. Hoping this will attract more people some of whom can give a nicer argument. – Jyrki Lahtonen Oct 15 '13 at 10:23

First, in reply to the observations in the question, it is indeed not true that every root in$~L$ of $X^{q+1}=\beta$ is a generator of $L^*$. The simplest example I found where this fails is for $q=5$: with $\beta=2$ some roots$~\alpha$ of $X^6=2$ in $\Bbb F_{25}$ satisfy $\alpha^2=3$ (one has $3^3\equiv2\pmod5$) and these$~\alpha$ only have order$~8$ in$~\Bbb F_{25}^*$. Indeed the polynomial $X^2-2$ factors over $\Bbb F_5$ as $X^6-2=(X^2-3)(X^4+3X+4)$, and only roots of the latter factor are generators of$~\Bbb F_{25}^*$.

As Jyrki's answer indicates, this really is just about cyclic groups. You have a surjective morphism of cyclic groups $C_{q^2-1}\to C_{q-1}$ (coming from raising to the $q+1$-st power), and you are asking if for every generator of $C_{q-1}$ there is some pre-image that is generator of $C_{q^2-1}$ (as you remarked it is obvious that the image of every generator is a generator). This is in fact true in the general case of a surjective morphism of groups $C_n\to C_d$. Choosing a generator of $C_n$ and its image as generator of $C_d$, the question becomes one of quotients of$~\def\Z{\Bbb Z}\Z$: for the morphism of additive groups $f:\Z/n\Z\to\Z/d\Z$ defined by (further) reduction modulo$~d$, is the induced map on the subsets of generators surjective?

The ring of endomorphisms of the Abelian group $\Z/n\Z$ is isomorphic to the ring $\Z/n\Z$, where the class of $a$ modulo$~n$ is identified with multiplication by$~a$ as endomorphism of the Abelian group $\Z/n\Z$. The group of automorphisms (invertible endomorphisms) corresponds to the multiplicative group $(\Z/n\Z)^\times$ of invertible elements in $\Z/n\Z$. A class modulo$~n$ is a generator of the cyclic group $\Z/n\Z$ if and only if it lies in $(\Z/n\Z)^\times$, so the question becomes whether the induced map $(\Z/n\Z)^\times\to(\Z/d\Z)^\times$ (still defined by reduction modulo$~d$) remains surjective. The point of view of endomorphisms is not needed for answering the question, but it shows that without identification with quotients of $\Z$ the question is equivalent to whether a surjective morphism of finite cyclic groups induces a surjective morphism of their automorphism groups: the invertible elements in the target cyclic group form an orbit under its automorphism group, and if such automorphisms are all induced by an automorphism of the source cyclic group, then the orbit is the image of an orbit under automorphisms in the source cyclic group.

That this induced map is indeed surjective can be proved using the Chinese remainder theorem (and I would not know any easy way to avoid using it). Let $m=\prod_{\text{prime }p\mid d}p^{v_p(n)}$ be the largest divisor of $n$ all of whose prime factors divide $d$. Factor $f$ as $\Z/n\Z\overset r\to\Z/m\Z\overset s\to\Z/d\Z$. One has $s^{-1}((\Z/d\Z)^\times)=(\Z/m\Z)^\times$: in lifting classes modulo$~d$ to classes modulo$~m$, every pre-image of an invertible element will be invertible; this is because class representatives are not divisible by any prime dividing$~m$ (and therefore$~d$), so they must be relatively prime with$~m$. Since $n/m$ and $m$ are relatively prime by construction, the Chinese remainder theorem gives an isomorphism of rings $\Z/n\Z\cong(\Z/m\Z)\times(\Z/(n/m)\Z)$ for which the morphism $r$ corresponds to projection onto the first factor; the isomorphism induces a morphsism of multiplicative groups $$(\Z/n\Z)^\times\cong(\Z/m\Z)^\times\times(\Z/(n/m)\Z)^\times.$$ The map induced by $r$ us still projection on the first factor, which is obviously surjective (since $(\Z/(n/m)\Z)^\times\neq\emptyset$). So we have factored the map induced by$~f$ into surjective maps $(\Z/n\Z)^\times\to(\Z/m\Z)^\times\to(\Z/d\Z)^\times$, and it is therefore surjective.

An alternative way to apply the Chinese remainder theorem is use it to decompose $\Z/n\Z$ into a product of rings $\Z/p^k\Z$ for prime powers $p^k$, so that it suffices to show for each prime individually that $\Z/p^k\Z\to\Z/p^l\Z$ induces a surjective map on the invertible elements whenever $0\leq l\leq k$. This is easily shown by treating separately the trivial case $l=0$; in the other cases again any pre-image of an invertible element is invertible.

-

The relevant result holds in a more general context of cyclic groups: If there is a surjective homomorphism from one finite cyclic group to another, then every generator of the range is the image of some generator of the domain.

I will first do it in that setting.

Let's assume that $m,d,k>1$ are all integers such that $m=dk$. We shall need the following three homomorphisms $$f:\Bbb{Z}_m\to\Bbb{Z}_k, \overline{x}\mapsto \overline{x},$$ $$g:\Bbb{Z}_m\to\Bbb{Z}_m, \overline{x}\mapsto \overline{dx}$$ and $$h:\Bbb{Z}_k\to\Bbb{Z}_m, \overline{x}\mapsto \overline{dx}$$ The first is a homomorphism of rings, the other two only of additive groups.

Proposition. The restriction $\tilde{f}$ of $f$ to the groups of units, $\tilde{f}:\Bbb{Z}_m^*\to\Bbb{Z}_k^*,$ is surjective.

This has surely been covered either in your textbook or on this site.

Let us denote by $S$ the set of generators of the group $g(\Bbb{Z}_m)=\langle \overline{d}\rangle\le\Bbb{Z}_m.$ We see that $S=h(\Bbb{Z}_k^*)$.

If $\overline{x}\in\Bbb{Z}_m^*$, then $\overline{dx}$ is of order $m/d=k$, so it generates the unique subgroup of order $k$, i.e. $g(\Bbb{Z}_m)$. Therefore $g(\Bbb{Z}_m^*)\subseteq S$. We can (and need to) say more.

Lemma. $g(\Bbb{Z}_m^*)=S$.

Proof. We can form the compostion $h^{-1}\circ g:\Bbb{Z}_m^*\to\Bbb{Z}_k^*$ that clearly equals $\tilde{f}$. As $h:\Bbb{Z}_k^*\to S$ is a bijection, the claim follows from this and the Proposition. QED

Corollary. If $C_m=\langle c\rangle$ and $H\langle c^d\rangle\le C_m$ are cyclic groups, and $r:C_m\to H$ is the homomorphism $r(c^i)=c^{di}$ (still assuming $m=dk$), then every generator $\beta$ of $H$ is of the form $r(\alpha)$ for some generator $\alpha$ of $C_m$.

Proof. This is the statement of the Lemma written in multiplicative form. QED

This settles the question in the OP. There $m=p^{2n}-1$, $d=p^n+1$, $k=p^n-1$.

We observe that the same argument works for all extensions of finite fields. Any primitive element of a finite field can be gotten as the image of some primitive element of any finite extension field under the relative norm map.

-
This is a quick'n dirty patchwork. Hopefully somebody can give a cleaner argument. – Jyrki Lahtonen Oct 15 '13 at 10:20