Welcome to our community

Be a part of something great, join today!

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

Bingk

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

Not sure how to go about this. I was thinking it might involve induction.
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.

Thanks in advance!
 
Last edited:

tkhunny

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

[tex]2^{n}[/tex] or [tex]2\cdot n[/tex]
 

Bingk

New member
Jan 26, 2012
16
Re: X^(2n) + x + 1 is reducible over Z2 for n>2

[tex]2^{n}[/tex]

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

Jameson

Administrator
Staff member
Jan 26, 2012
4,043
Re: X^(2n) + x + 1 is reducible over Z2 for n>2

[tex]2^{n}[/tex]

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

Opalg

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

Not sure how to go about this. I was thinking it might involve induction.
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.

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

Bingk

New member
Jan 26, 2012
16
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?