# Classes of primitive elements with the same minimal polynomial

This is problem 12.12 from "Error-Correcting Codes and Finite Fields" by Oliver Pretzel.

The problem:

If F is a field of order $p^k$, $p$ a prime, show that the primitive elements fall into classes of size $k$, where two primitive elements are in the same class if they have the same minimal polynomial. Deduce that $k|ϕ(p^k − 1)$.

I know $ϕ(p^k − 1)$ is the number of primitive elements of $F$

My guess would be I need to find a polynomial made up of all the distinct minimal polynomials and show that its degree is $ϕ(p^k − 1)$ and then divide this by the minimal polynomial of degree k and show that these are only divisible if $k|ϕ(p^k − 1)$

Any help would be appreciated.

• If $a$ is algebraic over a field $K$, then $K(a) \cong K[x]/(f(x))$ where $f$ is the minimal polynomial of $a$ Apr 19, 2017 at 1:40
• This is a somewhat pointless exercise. $k \mid \phi\left(p^k-1\right)$ holds for every integer $p > 1$, not just for primes, and this is easily seen through Lagrange's theorem (probably somewhere on m.se; the main idea is that $p$ has multiplicative order $k$ modulo $p^k-1$). Mar 31, 2019 at 4:34

If $\theta \in \mathbb{F}_{p^k}$ is a primitive element, then in particular $\theta$ is a generator for the extension $\mathbb{F}_{p^k}/\mathbb{F}_p$, i.e., $\mathbb{F}_{p^k} = \mathbb{F}_p(\theta)$. Since $[\mathbb{F}_{p^k} : \mathbb{F}_p] = k$, this shows that the minimal polynomial for $\theta$ has degree $k$, so it has $k$ distinct conjugates. (Every finite extension of $\mathbb{F}_p$ is separable.) In the language of the problem statement, this means that the class of $\theta$ has size $k$. These classes partition the set of primitive elements, which shows that the number of primitive elements is a multiple of $k$. Now you can use your observation that there are $\phi(p^k - 1)$ primitive elements to finish the problem.
(As an aside, your idea for an approach leads to a different result, namely that $x^{p^k} - x$ is the product of all irreducible polynomials over $\mathbb{F}_p$ of degree dividing $k$.)