I have seen that $x^{2}+x+1$ and $x^{4}+x+1$ are irreducible over $\mathbb{Z}_2$ and I thought a polynomial of the form $x^{2^m}+x+1$ for $m\ge3$ would be irreducible too. However using WolframAlpha, my hunch was wrong. It could be factored over $\mathbb{Z}_2$. WolframAlpha could only generate the factors for $m=3,\ldots, 13$ and so far, I observed that for odd $m$, my polynomial is divisible by $x^{2}+x+1$.
I want to see how one can show that $x^{2^m}+x+1$ for $m\ge3$ is reducible.
Best Answer
I will write $\mathbb F_2$ rather than $\mathbb Z_2$; here the $\mathbb F$ stands for "finite field" and the subscript is the number of elements in the finite field. This notation is convenient when one wants to consider larger finite fields, as I will in this answer.
The polynomial $x^2 + x + 1$ splits in the field $\mathbb F_4$ with $4$ elements; its two roots are the two elements of $\mathbb F_4$ that aren't in $\mathbb F_2$. Now if $\alpha \in \mathbb F_4$ then $\alpha^4 = \alpha$. Thus if $n = 2 m + 1 $ is odd, we have that $$\alpha^{2^{2m + 1}} = (\alpha^{4^m})^2 = \alpha^2,$$ and so $$\alpha^{2^{2m+1}} + \alpha + 1 = 0.$$ Consequently each of the two roots of $x^2 + x + 1$ is also a root of $x^{2^{2m+1}} + x + 1$ as well, which explains why $x^2 + x + 1$ divides $x^{2^{2m + 1}} + x + 1.$
To handle the general case of $x^{2^n} + x + 1$ (i.e. the case when $n$ is not necessarily odd) it helps to recall some Galois theory for finite fields. The key fact is that if $\alpha$ lies in any finite extension field of $\mathbb F_2$, namely some $\mathbb F_{2^f}$ for some $f \geq 1$, then the algebraic conjugates of $\alpha$ are all of the form $\alpha, \alpha^2,\alpha^4, \ldots.$ (This list will be finite, because --- assuming I chose $f$ minimally --- then $\alpha^{2^{f-1}} \neq \alpha,$ but $\alpha^{2^f} = \alpha$, and so $\alpha$ has exactly $f$ distinct conjugates over $\mathbb F_2$.)
Now suppose that $\alpha$ satisfies $$\alpha^{2^n} + \alpha + 1 = 0.$$ Adding $\alpha + 1$ to both sides (and remembering that $ 1 = - 1$ because we in characteristic $2$) we find that $$\alpha^{2^n} = \alpha+1.$$ Hence $$\alpha^{2^{2n}} = (\alpha^{2^n})^{2^n} = (\alpha + 1)^{2^n} = \alpha^{2^n} + 1 = (\alpha +1)+1 = \alpha$$ (using the facts that $(a+b)^2 = a^2 + b^2$ and $1 + 1 = 0$, which both hold in characteristic $2$).
So we see that the "$f$" for $\alpha$ is at most $2n$, i.e. $\alpha$ has at most $2n$ distinct algebraic conjugates over $\mathbb F_2$, and so its minimal polynomial over $\mathbb F_2$ has degree at most $2n$. Since $\alpha$ is a root of $x^{2^n} + x + 1$, this minimal polynomial divides $x^{2^n} + x + 1$. If $n \geq 3$, then $2n$ is strictly less than $2^n$, and so this minimal polynomial of $\alpha$ also has degree strictly less than that of $x^{2^n} + x + 1$. Thus when $n \geq 3,$ the polynomial $x^{2^n} + x + 1$ must be reducible.