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

Question

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 $.

Answer 1

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}$.

Answer 2

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.

Answer 3

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}} $.