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'm not certain how to go about this.
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 $\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$.)