# The number of elements $\alpha$ we can adjoin to a finite field $F$ to obtain an extension field.

Given finite field $\mathbb{F}_2$, consider the extension field $\mathbb{F}_{16}$ of $\mathbb{F}_2$, how many elements are there in $\mathbb{F}_{16}$ such that $\mathbb{F}_{16}=\mathbb{F_2}(\alpha)$?

In general, given finite field $\mathbb{F}_q$ where $q=p^r$ for $p$ prime. Given an extension field $\mathbb{F}_{q'}$ of $\mathbb{F}_q$: $\mathbb{F}_q\subset \mathbb{F}_{q'}$ where $q'=p^{rs}$. How many elements $\alpha\in\mathbb{F}_{q'}$ are there such that $\mathbb{F}_{q'}=\mathbb{F}_q(\alpha)$?

I know primitive elements are candidates. But there maybe exist more elements other than primitive elements that are also valid. For example, $\mathbb{F}_3\subset\mathbb{F}_9$, adjoining a square root of $-1$ to $\mathbb{F}_3$, $\mathbb{F}_9\cong\mathbb{F}_3(x)$ where $x^2+1=0$, but obviously $x$ is not a primitive element since $x^4=1$.

• Which elements of $\mathbb{F}_{16}$ do not generate $\mathbb{F}_{16}$ over $\mathbb{F}_2$? (What would they generate instead?) – ancientmathematician Apr 30 '18 at 15:01
• In addition to this comment: Remember that $\mathbb{F}(\alpha)$ is the smallest field over $\mathbb{F}$ that contains $\alpha$. – Verdruss Apr 30 '18 at 15:36
• @ancientmathematician Since the multiplicative group of a field is a cyclic group, for any field $\mathbb{F}_q$, there are exactly $\varphi(\varphi(q-1))$ primitive elements in the multiplicative group. Other than primitive elements, they will generate a proper subgroup of the multiplicative group. – Bach Apr 30 '18 at 16:09
• Think about: what are the subfields of your field? For which elements is your field the smallest field containing them? – Verdruss Apr 30 '18 at 16:21
• Forget the group. Which fields can an element of $\mathbb{F}_{16}$ lie in? – ancientmathematician Apr 30 '18 at 16:43

I’m not sure that your analysis of the situation in the general case is the most efficient. Here’s an explanation that makes use of the Möbius Inversion Formula.
(https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula)

Start with a field $K=K_n=\Bbb F_{p^n}$. As you know, the only subfields are those of the form $K_d=\Bbb F_{p^d}$ with $d|n$. Now let us put, for $d|n$, $\gamma(d)=$the number of elements of $K$ that generate $K_d$. We certainly have $\sum_{d|n}\gamma(d)=p^n$. And of course this is true for all $n$.

Now apply Möbius, to see that for every $n$, $\gamma(n)=\sum_{d|n}\mu(n/d)p^d$. That’s the Möbius function $\mu$ being used here, which is defined for square-free integers $n$ as $\mu(n)=(-1)^s$ if $n$ is the product of $s$ distinct primes, but $\mu(n)=0$ if $n$ is not square-free. It’s not too tricky to prove the formula.

In our case, you’re interested in $\gamma(n)$, as, for instance, $\gamma(6)=p^6-p^3-p^2+p$, equal to $64-8-4+2=54$ for the case of $\Bbb F_{64}$.

• Got it! Thank you professor~ – Bach May 1 '18 at 3:51

There is only one field between $\mathbb{F}_{2}$ and $\mathbb{F}_{16}$: it's $\mathbb{F}_{4}$. Therefore, every element in $\mathbb{F}_{16} \setminus \mathbb{F}_{4}$ generates $\mathbb{F}_{16}$ over $\mathbb{F}_{4}$. There are $16-4=12$ such elements.

To count the number of elements $\alpha\in\mathbb{F}_{16}$ such that $\mathbb{F}_2(\alpha)\cong\mathbb{F}_{16}$, we only need to exclude the situation that when $\alpha$ lies in a proper subfield of $\mathbb{F}_{16}$. In addiiton, $F$ is a proper subfield of a finite field $\mathbb{F}_{16}$ if and only if $F$ is contained in the field $\mathbb{F}_4$, since $16=2^4$ and it contains a proper subfield if and only if the degree of the subfield is a proper divisor of the degree of the field over the prime field which is $4$ here. Therefore there are $16-4=12$ elements of $\alpha$ satisfy the condition.

Generally, given finite field $\mathbb{F}_{q}$ where $q=p^r$ for $p$ prime. Given an extension field $\mathbb{F}_{q'}$ of $\mathbb{F}_q$: $\mathbb{F}_q\subset\mathbb{F}_{q'}$, where $q'=p^{rs}$. Suppose $s=\prod_{i=1}^k p_i^{a_i}, p_1<p_2<\cdots <p_k, a_i>0$ is the prime factorization of $r$, then there are exactly $p^{rs}-p^{\frac{rs}{p_1}}-p^{p_1}+p$ if $a_1=1$ and $p_1$ does not divide $r$; otherwise $p^{rs}-p^{\frac{rs}{p_1}}$.

• Your analysis doesn’t work for $k=\Bbb F_{p^6}$ (like $\Bbb F_{64}$). Can you see what the correct formulation is? – Lubin Apr 30 '18 at 21:30