6
$\begingroup$

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.

  • 0
    Yes, but the induction is not trivial for me. Since I can calculate the cubic roots easily, can You tell me how I can use that for $\mathbf{F_{2}} $ ? Because the complex cubic roots of 1 aren't in $\mathbf{F_{2}}$....2011-11-17

2 Answers 2

6

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$.

  • 0
    @AsafKaragila Thanks! I had to run off to dinner with my wife and kids and didn't have time to tweak the LaTeX. It looks a lot better :)2011-11-18
9

As a variation on the (essentially equivalent) ideas in the answers and comments: we could ask that there be $\alpha\in \mathbb F_4$ solving $x^n+x+1=0$, noting that certainly there is no solution in $\mathbb F_2$. For $\alpha\in \mathbb F_4$, $\alpha^4=\alpha$, and since $\alpha\not=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$.