The degree of an irreducible polynomial divides an integer n. Let $F$ be a finite field such that $|F|=q$, and $f(x)\in{F[x]}$ is irreducible with $deg(f)=d$, $g(x)=x^{{q}^{n}}-x$. Then prove that $f$ divides $g$ if and only if $d$ divides $n$. 
 A: The $d$ roots of $f(x)$ are conjugates, that is, if $f(\alpha) = 0$, then so are $f\left(\alpha^{q^1}\right), f\left(\alpha^{q^2}\right), \ldots, f\left(\alpha^{q^{d-1}}\right)$ all equal to $0$. Furthermore, $$\left(\alpha^{q^{d-1}}\right)^q = \alpha^{q^{d}} = \alpha,$$
that is, $\alpha^{q^d} - \alpha = 0$ and so $\alpha$ is also a root of $x^{q^d} - x$.  We conclude that $f(x)$ is a divisor of $x^{q^d} - x$, and just a little further thought shows that in fact $f(x)$ is a divisor of $x^{q^d-1} - 1$.
So we have that


*

*$f(x)$ is a divisor of $x^{q^d}-x$.

*$x^{q^d}-x$ is a divisor of $x^{q^n}-x = g(x)$ if and only if
$x^{q^d-1} - 1$ is a divisor of $x^{q^n-1} - 1$

*$x^{q^d-1} - 1$ is a divisor of $x^{q^n-1} - 1$ if and only if
$q^d-1$ is a divisor of $q^n-1$.
See the answers to $x^a - 1$ divides $x^b - 1$ if and only if $a$ divides $b$ if you don't know
this result.

*$q^d-1$ is a divisor of $q^n-1$ if and only if $d$ is a divisor of $n$.
Same reason as the previous claim.
We conclude that $f(x)$ is a divisor of $g(x) = x^{q^n}-x$ if and only
if $d =\deg(f)$ is a divisor of $n$.
