Show the polynomial is irreducible in $\textbf Z_2$

How's 'bout this:

Set

$p(x) = x^4 + x + 1 \in \Bbb Z_2[x]; \tag 0$

then

$p(\gamma) = \gamma^4 + \gamma+ 1 \ne 0 \tag 1$

for any $\gamma \in \Bbb Z_2$; therefore $p(x)$ has no factor of degree one in $\Bbb Z_2[x]$; thus if $p(x)$ is not irreducible, it be the product of two quadratics

$a(x) = a_2 x^2 + a_1 x + a_0 \in \Bbb Z_2[x], \tag 2$

and

$b(x) = b_2 x^2 + b_2 x + b_0 \in \Bbb Z_2[x]; \tag 3$

that is,

$p(x) = a(x)b(x); \tag 4$

it follows from (0), (2)-(4) that

$a_2 b_2 = 1 \tag 5$

and

$a_0 b_0 = 1; \tag 6$

now note that the only solutions to (5)-(6) in $\Bbb Z_2$ are

$a_2 = b_2 = a_0 = b_0 = 1; \tag 7$

thus

$a(x) = x^2 + a_1 x + 1, \tag 8$

$b(x) = x^2 + b_1 x + 1; \tag 9$

we have

$x^4 + x + 1 = p(x) = a(x)b(x) = (x^2 + a_1 x + 1)(x^2 + b_1 x + 1)$ $= x^4 + (a_1 + b_1)x^3 + 2x^2 + a_1 b_1 x^2 + (a_1 + b_1)x + 1$ $= x^4 + (a_1 + b_1)x^3 + a_1 b_1 x^2 + (a_1 + b_1)x + 1; \tag{10}$

comparing coefficients, it follows that

$a_1 + b_1 = 0, \tag{11}$

$a_1 b_1 = 0, \tag{12}$

and

$a_1 + b_1 = 1; \tag{13}$

clearly (11)-(13) have no solution in $\Bbb Z_2$; indeed (11) and (13) directly contradict each other, implying as they do $1 = 0$. Therefore no such polynomials $a(x)$, $b(x)$ exist in $\Bbb Z_2[x]$, and so $p(x)$ must be irreducible.

Note Added in Edit Sunday 24 September 2017 9:08 AM PST: This note addresses our OP Aldrec's comment to this answer, which in essence asks if a technique similar to that used above can be used to determine the reducibility/irreducibility over $\Bbb Z_2$ of the quintic polynomial

$q(x) = x^5 -x^4 + x^2 - x + 1; \tag{14}$

the answer is yes it can, as follows:

We first note that, over $\Bbb Z_2$, $q(x)$ may be written

$q(x) = x^5 + x^4 + x^2 + x + 1, \tag{15}$

since $-1 = 1$ in $\Bbb Z_2$. The form (15) of $q(x)$ will make the arithmetic and bookkeeping a little easier. Next we see that

$q(0) = q(1) = 1, \tag{16}$

which shows that $q(x)$ has no root in $\Bbb Z_2$, hence no linear factor in $\Bbb Z_2[x]$. So if $q(x)$ is reducible, it must have on quadratic and one cubic factor. To investigate this prospect, we set

$a(x) = a_2x^2 + a_1x + a_0 \tag{17}$

and

$b(x) = b_3x^3 + b_2 x^2 + b_1 x + b_0, \tag{18}$

and set

$q(x) = a(x)b(x) = (a_2x^2 + a_1x + a_0)(b_3x^3 + b_2 x^2 + b_1 x + b_0); \tag{19}$

before proceeding any further we see by comparing (19) and (15) that we must have

$a_2b_3 = a_0b_0 = 1, \tag{20}$

which implies

$a_2 = b_3 = a_0 = b_0 = 1; \tag{21}$

substituting these values into (19) yields

$q(x) = (x^2 + a_1x + 1)(x^3 + b_2x^2 + b_1x + 1); \tag{22}$

we next perform the multiplication indicated on the right of (22) and see that

$x^5 + x^4 + x^2 + x + 1 = q(x) = a(x)b(x) = (x^2 + a_1x + 1)(x^3 + b_2x^2 + b_1x + 1)$ $= x^5 + (a_1 + b_2)x^4 + (b_1 + a_1 b_2 + 1)x^3 + (a_1b_1 + b_2 + 1)x^2 + (a_1 + b_1)x + 1, \tag{23}$

and so we conclude that

$a_1 + b_2 = a_1b_1 + b_2 + 1 = a_1 + b_1 = 1 \tag{24}$

and

$b_1 + a_1 b_2 + 1 = 0. \tag{25}$

It is easy to see that (24), (25) have no solution in $\Bbb Z_2$; if $a_1 = 0$, (24) yields

$b_2 = b_2 + 1, \tag{26}$

clearly impossible; whereas if $a_1 = 1$, (24) forces

$b_1 = b_2 = 0, \tag{27}$

which contradicts (25). We conclude there are no polynomials $a(x), b(x) \in \Bbb Z_2[x]$ satisfying (19); thus $q(x)$ is irreducible over $\Bbb Z_2$. End of Note.

$x^4+x+1$ clearly has no root in $\mathbb{F}_2$. Since the only quadratic irreducible polynomial over $\mathbb{F}_2$ is $x^2+x+1$ and $x^2+x+1$ is not a divisor of $x^4+x+1$, $x^4+x+1$ is irreducible over $\mathbb{F}_2$.

Robert Lewis did a great job, but I think that his exposition could perhaps be shortened. Consider $$ p(x)=x^4+x+1 \in \mathbb{Z}_2[x] $$ Since $p(0)=1$ and $p(1) = 1$, the original $p(x)$ has not root and thus cannot be factored into the product of a cubic and a first degree polynomial.

If it could be factored, then both quadratics would have to be of the form: $$ x^2+ax+1 $$ because the first and last coefficients of both quadratics multiply up to unity in $\mathbb{Z}_2$. If either of the two quadratics had $a=0$, then $p(1)=0$, contradicting the fact that $p(x)\in \mathbb{Z}_2[x]$ has no roots. And if both quadratics had $a=1$, then $p(x)$ would have to have non-zero coefficients for the $x^3$ and $x^2$ terms, again a contradiction.