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

[Bingk1]

If n \geq 3, prove that x^{2^n} + x + 1 is reducible over \mathbb{Z}_2.

Not sure how to go about this. I was thinking it might involve induction.
For n=3, we have
x^8+x+1=(x^2+x+1)(x^6+x^5+x^3+x^2+1), but I can't find any pattern to help with the induction.

Thanks in advance!

 

[tkhunny]

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

2^{n} or 2\cdot n

 

[Bingk1]

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]

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]

If n \geq 3, prove that x^{2^n} + x + 1 is reducible over \mathbb{Z}_2.

Not sure how to go about this. I was thinking it might involve induction.
For n=3, we have
x^8+x+1=(x^2+x+1)(x^6+x^5+x^3+x^2+1), but I can't find any pattern to help with the induction.

Thanks in advance!

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

 

[Bingk1]

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?