<s>[INST] Show that there are infinitely many reducible polynomials of the form $x^n+x+1$ in $\mathbf{F}_2[x]$ Here is a question from an old exam:

Show that there are infinite $n\in \mathbf{N}, A= x^{n}+x+1 $ which are reducible over  $\mathbf{F}_{2}[x]$. 

Using André Nicolas' and Qiaochu Yuan's hint: $x^{2}+x+1$ as dividing polynomial. $x^{2}+x+1$ is irreducible over $\mathbf{F_{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 $\mathbf{F_{2}}$ the polynomial belongs to the residue class $\tilde{1}$, therefore there must be an infnite amount of them.
Concerning Gerry Myerson's hint, how can I use cubic roots in $\mathbf{F_{2}}$, wouldn't I need $\mathbf{R}[i]$ for that? 
Help is greatly appreciated. 
 [/INST] Proof by induction.
Base case ($n=0$):
$$\begin{align}
(x^2+x+1)\left(x^3+\sum\limits_{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
\end{align}$$ (working in $\mathbb{F}_2[x]$).
Inductive hypothesis ($n \geq 0$):
Suppose that $$(x^2+x+1)\left(x^{3(n+1)}+\sum\limits_{i=0}^n (x^{3i}+x^{3i+2})\right)=x^{3n+5}+x+1$$
Then:
$$\begin{align}
&(x^2+x+1)\left(x^{3(n+2)}+\sum\limits_{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}+\sum\limits_{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)}+\sum\limits_{i=0}^{n} (x^{3i}+x^{3i+2})\right)
\end{align}$$
using our inductive hypothesis we get
$$\begin{align}
&=(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
\end{align}$$
Therefore, $x^{3(n+1)+5}+x+1$ is reducible in $\mathbb{F}_2[x]$ (or in any polynomial ring with coefficients in a field of characteristic 2) for all non-negative integers $n$.
</s>