Subscribe via feed.

## 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 ?

This post is under “MathsChallenge” and has 7 respond so far.

### 7 Responds so far- Add one»

1. 1. Carc Said：

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

2. 2. Carc Said：

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

3. 3. Chris Said：

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)

4. 4. jan Said：

(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?

5. 5. jan Said：

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

6. 6. jan Said：

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

7. 7. Chris Said：

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.

PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0