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.

  • 2
    Try to pick a quadratic polynomial $p$ with the property that $p | x^n + x + 1$ for infinitely many $n$.2011-11-16
  • 1
    Maybe you should re-word the title of your question. An _infinite amount_ of reducible polynomials?2011-11-16
  • 2
    A variant of Qiaochu's hint: let $\alpha\ne1$ be a complex cube root of 1. For which values of $n$ is $\alpha$ a zero of $x^n+x+1$?2011-11-16
  • 0
    Gerry, if $\alpha$ is $(-1)^{2/3}$, then for $n=3m-1$ $\alpha^{n}+\alpha+1=0$ is satisfied. I don't see how to continue with this result, thanks though. :) :)2011-11-17
  • 1
    So if a polynomial has a root, then it has a factor; two factors in this case, since there are two of these cube roots of 1.2011-11-17
  • 2
    Look at $x^5+x+1=x^5-x^2+(x^2+x+1)$. Show that $x^2+x+1$ divides this polynomial. (The $-x^2$ is of course the same as $x^2$, just looks nicer.) Then look at $x^8+x+1=x^8-x^5+(x^5+x+1)$.2011-11-17
  • 0
    Continuing Gerry's hint, is it right to conclude that since there are two such cubes, the polynomial itself is reducible over $\mathbf{Z}[i]$, and thus also reducible over $\mathbf{F_{2}}$. :) :) With André Nicolas' hint, I can shoew that x^{2}+x+1 divides x^{5}-x^{2}+(x^{2}+x+1) by using polynomial division. Same goes for $x^{8}+x+1 and x^{5}+x+1$. Would a proof by induction, that every polynomial of the form: $x^{5n+3}+x+1=x^{5n+3}-x^{5n}+(x^{5n}+x+1)$ is reducible solve the problem over $\mathbf{F_{2}}$? Thanks. To both of You. :) :)2011-11-17
  • 0
    If a polynomial is reducible over the integers, don't you reckon that has consequences over the field of two elements?2011-11-17
  • 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
    The $\LaTeX$ was too long, so I tried to make it nicer while I chopped down the lines... I hope you don't mind.2011-11-17
  • 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
8

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