Factoring $x^{16}-x$ over $\mathbb{F}_8$ A homework question asks me to factor $x^{16}-x$ over the finite fields $\mathbb{F}_4$ and $\mathbb{F}_8$.  I got the result for $\mathbb{F}_4$ using the factoring over $\mathbb{F}_2$ and then a lengthy argument by exhaustion to find how the quartic factors over $\mathbb{F}_2$ split into quadratic factors over $\mathbb{F}_4$.  This same line of argument doesn't work again for $\mathbb{F}_8$, just because there are far more possible irreducible factors.  I am able to get as far as $x (x-1) (x^2+x+1) (x^4+x^3+1) (x^4+x+1) (x^4+x^3+x^2+x+1)$, which is the factoring over $\mathbb{F}_2$.  However, looking for quadratic factors of those final three terms is far harder over $\mathbb{F}_8$ than over $\mathbb{F}_4$ using my near-brute-force methods.
 A: Key fact: if $f(x)$ is an irreducible polynomial of degree $d$ over the finite field $\Bbb F_{p^r}$, and $\alpha$ is a root of $f(x)$, then $\Bbb F_{p^r}[\alpha]$ is isomorphic to $\Bbb F_{p^{rd}}$. In particular, $\alpha$ is an element of $\Bbb F_{p^{rd}}$.
Related fact: $\Bbb F_{p^r}$ is a subfield of $\Bbb F_{p^s}$ if and only if $r$ divides $s$ (note - not $r\le s$).
For example, given your factorization of $x^{16}-x$ over $\Bbb F_{2}$, we know that two of its roots are in $\Bbb F_{2}$, two more are in $\Bbb F_{4}$, and the other twelve are in $\Bbb F_{16}$. Indeed, the 16 elements of $\Bbb F_{16}$ are precisely the roots of $x^{16}-x$.
This also tells you (without any lengthy calculations) that each quartic factor over $\Bbb F_{2}$ splits into two quadratic factors over $\Bbb F_{4}$.
Finally, we can deduce from these facts that any quartic factor over $\Bbb F_{2}$ must remain quartic over $\Bbb F_{8}$. Certainly there are no roots in $\Bbb F_{8}$, so the only possibility to rule out is a splitting into two quadratic factors. If this happened, though, then let $\alpha$ be a root of one quadratic factor; we then have $\Bbb F_{8}[\alpha]=\Bbb F_{64}$. But $\alpha$ is also a root of the original quartic factor over $\Bbb F_{}$ and hence lies in $\Bbb F_{16}$. But the intersection of $\Bbb F_{64}$ and $\Bbb F_{16}$ (in a fixed algebraic completion) is just $\Bbb F_{4}$, which is a contradiction because $\alpha$ cannot be in $\Bbb F_{4}$.
