Find an irreducible polynomial of degree $21$ in $\mathbb{F}_2[x]$ Note: this is from a paper on Galois Theory, so I believe the technique will come from Galois... Possibly.
I am going to reduce it to the monic case: $x^{21}+a_{20}x^{20}+... a_0$ where all $a_i$ belong to $\{0,1\}$ . I was thinking of trying to generate a polynomial that would satisfy Eisenstein's criterion but it cannot have any prime coefficients.
The easiest starting points are $x^{21}+x$, $x^{21}+x+1$, $x^{21}+x^2$ ...etc 
I do not know how to check that these are irreducible without Eisenstein's criterion.. Is it true that since the highest power is odd, if it were irreducible, then it would have a linear factor. So can we just plug in values of $0$ and $1$ until we find a polynomial that gives us a non -zero answer?
So for example, can we say that $f(x)=x^{21}+x+1$ is irreducible, since $f(0)=f(1)=1 \neq 0$?
Is it possible to use Galois Theory to answer these questions?
 A: The following trick springs to mind.
We know that the minimal polynomials of seventh roots of unity are the cubic irreducibles
$$
p_1(x)=x^3+x+1\qquad\text{and}\qquad p_2(x)=x^3+x^2+1.
$$
Now, because $2$ is of order $21$ modulo $49$ (leaving it to you to check that), we can deduce (Galois theory is all we need here) that:


*

*The 49th roots of unity generate the field $\Bbb{F}_{2^{21}}$.

*Hence their minimal polynomials are irreducible of degree $21$.

*Hence their minimal polynomials are (drums, please)
$$
p_1(x^7)=x^{21}+x^7+1\qquad\text{and}\qquad p_2(x^7)=x^{21}+x^{14}+1.
$$

A: Using the Berlekamp algorithm it follows that
$$
x^{21}+x+1=(x^{14} + x^{12} + x^7 + x^6 + x^4 + x^3 + 1)(x^7 + x^5 + x^3 + x + 1)
$$
over $\mathbb{F}_2$, hence it is reducible. However,
$$
g(x)=x^{21}+x^2+1
$$
is irreducible over $\mathbb{F}_2$.
A: About your very last question (with fields extensions theory, in fact): 
we know $\;\Bbb F_{2^{21}}\cong\Bbb F_2[x]/{p(x)}\;$ , with $\;p(x)\in\Bbb F_2[x]\;$  irreducible. But we also know that $\;\Bbb F_{2^{21}}\;$ is the
splitting field over its prime field of $\;x^{2^{21}}-x\in\Bbb F_2[x]\;$ , so it must be that $\;p(x)\;$ is among the
divisors of this last polynomial.
Anyway, it doesn't look like an enjoyable task.
A: We may take two irreducible polynomials over $\mathbb{F}_2$:
$$ p_\alpha(x)=x^3+x+1,\qquad p_\beta(x)=x^7+x+1 $$
and by assuming that $\alpha$ is a root of $p_\alpha$, $\beta$ is a root of $p_\beta$, just compute the minimal polynomial, over $\mathbb{F}_2$, of $\alpha+\beta$. Since $[\mathbb{F}_2(\alpha):\mathbb{F}_2]=3,\, [\mathbb{F}_2(\beta):\mathbb{F}_2]=7$ and $\gcd(3,7)=1$, $[\mathbb{F}_2(\alpha+\beta):\mathbb{F}_2]=21$ as wanted. 
We just have to represent $(\alpha+\beta)^k$, for $k\in\{0,1,2,\ldots,20,21\}$, as a linear combination of $\alpha^i \beta^j$, with $i\in\{0,1,2\}$ and $j\in\{0,1,\ldots,6\}$, then perform Gaussian elimination.
