# X^(2^n) + x + 1 is reducible over Z2 for n>2

#### Bingk

##### New member
If [TEX]n \geq 3[/TEX], prove that [TEX]x^{2^n} + x + 1[/TEX] is reducible over [TEX]\mathbb{Z}_2[/TEX].

For [TEX]n=3[/TEX], we have
[TEX]x^8+x+1=(x^2+x+1)(x^6+x^5+x^3+x^2+1)[/TEX], but I can't find any pattern to help with the induction.

Last edited:

#### tkhunny

##### Well-known member
MHB Math Helper
Re: X^(2n) + x + 1 is reducible over Z2 for n>2

$$2^{n}$$ or $$2\cdot n$$

#### Bingk

##### New member
Re: X^(2n) + x + 1 is reducible over Z2 for n>2

$$2^{n}$$

I tried editing the title, but it didn't save the change

#### Jameson

Staff member
Re: X^(2n) + x + 1 is reducible over Z2 for n>2

$$2^{n}$$

I tried editing the title, but it didn't save the change
Done

#### Opalg

##### MHB Oldtimer
Staff member
If [TEX]n \geq 3[/TEX], prove that [TEX]x^{2^n} + x + 1[/TEX] is reducible over [TEX]\mathbb{Z}_2[/TEX].

For [TEX]n=3[/TEX], we have
[TEX]x^8+x+1=(x^2+x+1)(x^6+x^5+x^3+x^2+1)[/TEX], but I can't find any pattern to help with the induction.

For odd values of $n$, $1+x+x^2$ is a factor. In fact, $$(1+x+x^2)\bigl(1+(x^2+x^3+x^5+x^6)(1+x^6+x^{12} + \ldots + x^{6k})\bigr) = 1+x+x^{6k+8}.$$ If you then choose $k=\frac13(2^{2r}-4)$ (which is always an integer), then $6k+8 = 2^{2r+1}$. Thus you have a factorisation for $1+x+x^{2^{2r+1}}.$

But I have made no progress at all in the case where $n$ is even. In particular, I have been completely unable to factorise $1+x+x^{16}.$

#### Bingk

##### New member
I got stuck on that one too, that's why I couldn't proceed. I thought I'd get into trouble with higher powers, so I didn't check those. Thanks again!

Just curious, is there any method you're using to factorize the polynomial?

I'm basically doing a systematic guessing, is there any other way?