Vtyjkyuk

Here is a question from an old exam:

Show that there are infinite $nin mathbfN, A= x^n+x+1 $ which are reducible over $mathbfF_2[x]$.

Using André Nicolas' and Qiaochu Yuan's hint: $x^2+x+1$ as dividing polynomial. $x^2+x+1$ is irreducible over $mathbfF_2$. If an irreducible polynomial divides another polynomial which is not itself, that means that polynomial must be reducible. We want to show that $x^2+x+1$ divides all polynomials of the form $x^3n+5+x+1$. I can't figure the induction steps, but in $mathbfF_2$ the polynomial belongs to the residue class $tilde1$, therefore there must be an infnite amount of them.

Concerning Gerry Myerson's hint, how can I use cubic roots in $mathbfF_2$, wouldn't I need $mathbfR[i]$ for that?

Help is greatly appreciated.

Proof by induction.

Base case ($n=0$):
$$beginalign
(x^2+x+1)left(x^3+sumlimits_i=0^0 (x^3i+x^3i+2)right)&=(x^2+x+1)(x^3+x^2+1)\&=x^5+2x^4+2x^3+2x^2+x+1\&=x^5+x+1=x^3(0)+5+x+1
endalign$$ (working in $mathbbF_2[x]$).

Inductive hypothesis ($n geq 0$):
Suppose that $$(x^2+x+1)left(x^3(n+1)+sumlimits_i=0^n (x^3i+x^3i+2)right)=x^3n+5+x+1$$

Then:
$$beginalign
&(x^2+x+1)left(x^3(n+2)+sumlimits_i=0^n+1 (x^3i+x^3i+2)right)=\
&(x^2+x+1)left(x^3(n+2)+x^3(n+1)+x^3(n+1)+2+sumlimits_i=0^n (x^3i+x^3i+2)right)=\
&(x^2+x+1)(x^3(n+2)+x^3(n+1)+2) +
(x^2+x+1)left(x^3(n+1)+sumlimits_i=0^n (x^3i+x^3i+2)right)
endalign$$

using our inductive hypothesis we get

$$beginalign
&=(x^2+x+1)(x^3(n+2)+x^3(n+1)+2) + x^3n+5+x+1\
&=(x^2+x+1)(x^3n+6+x^3n+5) + x^3n+5+x+1\
&=x^3n+8+2x^3n+7+2x^3n+6+2x^3n+5+x+1\
&=x^3(n+1)+5+x+1
endalign$$

Therefore, $x^3(n+1)+5+x+1$ is reducible in $mathbbF_2[x]$ (or in any polynomial ring with coefficients in a field of characteristic 2) for all non-negative integers $n$.

As a variation on the (essentially equivalent) ideas in the answers and comments: we could ask that there be $alphain mathbb F_4$ solving $x^n+x+1=0$, noting that certainly there is no solution in $mathbb F_2$. For $alphain mathbb F_4$, $alpha^4=alpha$, and since $alphanot=0,1$, also $alpha^3=1$ and $alpha^2+alpha+1=0$. Thus,
$$
alpha^3n+2 + alpha + 1 = alpha^2+alpha+1 = 0
$$
Thus, $x^2+x+1$ divides $x^3n+2+x+1$.