Counting primitive elements in a finite field extension

Question

I want to find the no. of elements $\alpha \in \mathbb{F}_{3^5}$ so that $\mathbb{F}_{3}(\alpha) = \mathbb{F}_{3^5}$(minimal polynomial of $\alpha$ is of degree 5). I know such things do exist but how to count them?

I need to basically know how man irreducible factors of $x^{3^5}-x$ are of degree $5$ (over $\mathbb{F}_{3}$).

By ad hoc method I am getting for $\mathbb{F}_{2^4}$ the answer is $12$ since the minimal polynomial can only have irreducible polynomials whose degree divides $4$ and so there are 3 degree $4$ and $1$ degree 2(other combinations dont work due to size of $\mathbb{F}_{4}$).

Answer 1

Given any element $a\in\mathbb F_{p^n}\setminus \mathbb F_p$ whose degree over $\mathbb F_p$ is $d>1$, we have $\mathbb F_{p^n}$ is a vector space over $\mathbb F[a]$, hence $|\mathbb F_{p^n}|=|\mathbb F[a]|^m=p^{dm}\Rightarrow n=dm$ for some natural number $m$.

When $n$ is a prime number (such as $5$ in your case), there must be $d=n$ as $d|n$ and $d>1$. That is, there is no intermediate field between $\mathbb F_p$ and $\mathbb F_{p^n}$. In particular, the number of elements with degree $n$ is exactly $p^n-p$.

When $n$ is not a prime number, we need to use a more complicated analysis related to the factorization of $n$.

Answer 2

I am posting a general answer as suggested by Jyrki Lahtonen,

The facts we need:

1. All elements of $\mathbb{F}_{p^n}$ are roots of $x^{p^n} - x$ in some algebraic closure over $\mathbb{F}_{p}$.

2. $\mathbb{F_{q}}$ is a subfield of $\mathbb{F}_{p^n}$ IFF $q= p^m$ for some $m$ dividing $n$ and their is a unique such subfield. One can proof the uniqueness using the fact that these are also cyclic groups(under multiplication omitting the zero).

So, the irreducible factors of $x^{p^n}-x$ will only have degree $k$ dividing $n$.

Every element leads to an extension of the possible degree mentioned and by uniqueness we get (denoting the answer to be $f(m)$ for $\mathbb{F}_{p^m}$):

$\sum _{d | n} f(d) = p^{n}$.

One can apply Mobius inversion to get a more explicit formula.