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.
If you enjoy this article, make sure you subscribe to my RSS Feed.

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.

Post a reply




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