Polynomial of degree 4 over $\mathbb{F}_2$ has a root in $\mathbb{F}_{16}$ In my textbook it says that it is clear that polynomials of degree 4 over $\mathbb{F}_2$ have always roots in $\mathbb{F}_{16}$. How does this work, since it is not true for example for polynomials of degree $5$ over $\mathbb{F}_2$ in $\mathbb{F}_{32}$? Is there a simple proof?
 A: The finite fields of charachteristic $p$ are related by the fact that $\Bbb F_{p^m}\subseteq \Bbb F_{p^n}\Leftrightarrow m\mid n$. Now, it is certainly the case that any irreducible polynomial of degree $n$ in $\Bbb F_p[T]$ has splitting field $\Bbb F_{p^n}$; however, the splitting field of a polynomial $f$ of degree $n$ may not be $\Bbb F_{p^n}$ when the polynomial is reducible: in fact, it will be $\Bbb F_{p^{\operatorname{lcm}(n_1,\cdots,n_k)}}$, where $n_1,\cdots, n_k$ are the degrees of the irreducible factors of $f$ in $\Bbb F_p[T]$.
Now, the reason why a polynomial of degree $4$ in $\Bbb F_2[T]$ has roots in $\Bbb F_{16}[T]$ is simply the fact that the possible degrees for a factorization of $f$ are:


*

*$4$;

*$3+1$;

*$2+2$;

*$2+1+1$;

*$1+1+1+1$.


In all cases, one of the irreducible factors will split either in $\Bbb F_{2^4}$, or in $\Bbb F_{2^1}$, or in $\Bbb F_{2^2}$, all of which are subfields of $\Bbb F_{16}$. On the other hand, a polynomial of degree $5$ may split with degrees $3+2$, and this arrangement does not generate subfields of $\Bbb F_{2^5}$.
Added: Along this line of thought, though, it is easy to give the rough estimate that a polynomial of degree $n$ in $\Bbb F_p[T]$ has a root in $\Bbb F_{p^{n\cdot\lfloor n/2\rfloor!}}$.
A: Hint: Show that a polynomial of degree four always has an irreducible factor of degree that is a factor of four.
A: Consider how a polynomial of degree $5$ could possibly fail to have roots in $\Bbb F_{32}$: It must be the product of an irreducible square polynomial and an irreducible cubic, thus having roots in $\Bbb F_4$ and $\Bbb F_{8}$, neither of which are subfields of $\Bbb F_{32}$.
It's not too difficult to see that this failure cannot happen for degree $4$ and $\Bbb F_{16}$, as $\Bbb F_4$ is a subfield of $\Bbb F_{16}$.
A: Recall that $\mathbb{F}_{p^r}$ is contained in $\mathbb{F}_{p^s}$ if and only if $r|s$.
Say $p(x)$ has degree $4$. If it is irreducible, then its splitting field is $\mathbb{F}_{2^4}$, so you are fine. If it is reducible, then it either has a linear factor (and that root is certainly in $\mathbb{F}_{2^4}$ well), or is a product of two irreducible quadratics; the irreducible quadratics split over $\mathbb{F}_{2^2}$.
For degree $5$ the argument doesn’t work because if $p(x)$ factors into an irreducible quadratic and an irreducible cubic, the roots are in $\mathbb{F}_{2^2}$ and in $\mathbb{F}_{2^3}$, neither of which is contained in $\mathbb{F}_{2^5}$.
