## A harder polynomial problem

Posted by Chris on November 20, 2011 – 4:07 pm

What is the remainder when (x + 1)^2010 is divided by x^2 + x + 1 ?

Posted by Chris on November 20, 2011 – 4:07 pm

What is the remainder when (x + 1)^2010 is divided by x^2 + x + 1 ?

November 20th, 2011 at 4:25 pm

this looks very easy to me, isn’t it simply (x+1)^2008?

November 20th, 2011 at 4:29 pm

oh, forget it, i misread the divisor to be x^2+TWOx+1

November 20th, 2011 at 6:37 pm

As this one is unusual compared to much of the stuff on this site, I’ll give the following clues:

Determine x + 1 (mod x^2 + x + 1)

x^3 – 1 = (x – 1)(x^2 + x + 1)

November 22nd, 2011 at 3:12 am

(x+1)*(x+1)=x^2+2x+1

mod(x^2+2x+1,x^2+x+1)=x

so mod((x+1)^2010,x^2+x+1)=x^1005

does this help?

November 22nd, 2011 at 3:38 am

(x+1)^2010 -> x^1005 -> x*(-x-1)^502 -> x^252 -> (-x-1)^126 -> x^63 -> x*(-x-1)^31 ->(-x-1)*x^16 -> (-x-1)^9 -> (-x-1)*x^4 -> (-x-1)^3 -> (-x-1)*x = -x^2-x -> 1

Continuing the same way i get a rest of 1.

November 22nd, 2011 at 3:39 am

i don’t see how the hints are useful so i may have chosen a wrong path.

November 22nd, 2011 at 7:08 am

Hi jan. Good work. I like your (x+1)^2 = x (mod x^2+x+1). That’s a

better observation that the one I was going for. As you say, that =>

(x+1)^2010 = x^1005 (mod x^2 + x + 1)

In turn that = (x^3)^335 (mod x^2 + x + 1)

Using x^3 – 1 = (x – 1)(x^2 + x + 1) = 0 (mod x^2 + x + 1) =>

x^3 = 1 (mod x^2 + x +1)

So (x+1)^2010 = (x^3)^335 = 1^335 = 1 (mod x^2 + x + 1)

That’s a bit neater than the way I’d done it originally.

The way I’d gone was x^2 + x + 1 = 0 (mod x^2 + x + 1)

=> x + 1 = -x^2 (mod x^2 + x + 1)

=> (x+1)^2010 = (-x^2)^2010 (mod x^2 + x + 1)

= x^4020 = (x^3)^1340 = 1 (mod x^2 + x + 1)

where I used x^3 = 1 (mod x^2 + x + 1)

So the remainder is 1.

NB I’ve tacitly assumed that x^2 + x + 1 ≠ 0.