Finite extensions of finite fields always generated by cyclotomic type polynomials I've been trying to solve the following problem, but I am having troubles with the backward implication.
If $|K| = q$ and $f \in K[x]$ is irreducible, then $f$ divides $x^{q^n} - x$ if and only if $\text{deg}(f)$ divides $n$.
My idea: For the direct implication, we take $L$ to be the extension of $K$ of degree $n$. That extension is unique up to $\mathbb{Z}_p$-isomorphism, and it is precisely the splitting field of $x^{q^n} - x$. Since $f$ divides $x^{q^n} - x$, all the roots of $f$ are in $L$, which means that $K(u_1)$ is an intermediate extension of $L/K$, where $u_1$ is a root of $f$. Clearly, $[K(u_1):K] = \text{deg}f$, and the direct implication follows.
For the backward implication I am super confused because any finite extension of a finite field is the splitting field of a polynomial of the form $x^{p^n} - x$, but in this problem we are trying to prove that $f$ which is an arbitrary irreducible polynomial divides an expression like the one before. That led me to think that $f$ is generated by the multiplication of terms of the form $(x - \zeta)$ where $\zeta$ is a root of unity. Anyway, any ideas for the backward implication and my philosophical question? 
 A: One route. Do tell me if a step needs something you have not covered.
So we assume that $f(x)$ is irreducible over $K$, and $m=\deg f(x)$ is a factor of $n$. Then 


*

*$F=K[x]/(f(x))$ is a field of $q^m$ elements.

*$u=x+(f(x))$ is a zero of $f(x)$ in the field $F$, and $f(x)$ is the minimal polynomial of $u$ over $K$.

*All the elements of $F$ are zeros of $P_m(x):=x^{q^m}-x$.

*Therefore $P_m(x)$ and $f(x)$ share a common zero $u$ in the field $F$.

*Therefore $P_m(x)$ and $f(x)$ have a non-trivial common factor.

*Both $P_m(x)$ and $f(x)$ have coefficients in $K$, so, by Euclid's algorithm, their highest degree common divisor, call it $g(x)=\gcd(P_m(x),f(x))$, also has coefficients in $K$.

*As $u$ was a common zero of $P_m$ and $f$, we also have $g(u)=0$.

*Because $f$ is the minimal polynomial of $u$ over $K$ we can conclude that $f(x)$ is a factor of $g(x)$. Clearly $g(x)\mid f(x)$, so $g(x)$ and $f(x)$ are equal up to a non-zero constant multiplier.

*As $g(x)$ is a factor of $P_m(x)$, so is $f(x)$.

*As $m\mid n$, $P_m(x)$ is a factor of $P_n(x)$. Hence $f(x)\mid P_n(x)$.


This is probably overkill in the number of steps. Depending on how familiar you are with making deductions like these about divisibility of polynomials you may be able to do several steps at once. I tried to break it into tiny steps. Don't know if that is pedagogically optimal.


In finite fields we are often lead to looking at cyclotomic polynomials (and their factors over a finite field). This is natural because all the non-zero elements of all the finite fields are roots of unity.

