Testing irreducibility in finite fields 
Let $P(x) = x^4 + x^3 + 1$. Is it irreducible over $\mathbb F_8$?

I know it is reducible over $\mathbb F_4$.
 A: That polynomial is, indeed, irreducible over $\Bbb{F}_2$, but as $2\mid 4$ this quartic will factor over the degree $2$ extension $\Bbb{F}_4$. More precisely,
if $\omega$ is a third root of unity $\in\Bbb{F}_4$, then $\omega^2=\omega+1$.
Consequently
$$
\begin{aligned}
(x^2+\omega x+\omega)(x^2+\omega^2x+\omega^2)&=x^4+(\omega+\omega^2)x^3+(\omega^2+\omega^2+\omega)x^2+(\omega^3+\omega^3)x+\omega^3\\
&=x^4+x^3+1.
\end{aligned}
$$
On the other hand, this quartic is irreducible over $\Bbb{F}_8$ because $\gcd(3,4)=1$. Galois theory gives this latter result. If $\gamma$ is one of the zeros of $P(x)$ in $\Bbb{F}_{16}$, then the other zeros are $\gamma^2$, $\gamma^4$ and $\gamma^8$ (but $\gamma^{16}=\gamma$). All those four zeros are also conjugate over $\Bbb{F}_8$. This is because the automorphism $F:x\mapsto x^8$ also permutes them in a 4-cycle (though in opposite order from that of the automorphism $x\mapsto x^2$). 
Note that the automorphism $x\mapsto x^4$ would partition them into two 2-cycles, and over $\Bbb{F}_4$ the two quadratic factors are (in some order)
$$P(x)=\biggl((x-\gamma)(x-\gamma^4)\biggr)\biggl((x-\gamma^2)(x-\gamma^8)\biggr).$$

A general result is that a polynomial $P(x)$ of degree $n$, irreducible over the prime field $\Bbb{F}_p$, splits over $\Bbb{F}_{p^m}$ into factors of degree
$n/\gcd(n,m)$. This is seen by studying the action of the Galois group on the roots.
