Tuesday, September 29, 2009

Polynomial remainder

Find the remainder when x^1000 is divided by x^4 - x^2 + 1.

1 comment:

  1. The answer is x^2 - 1.

    x^1000 = (x^4)(x^996 - 1) + x^4
    = (x^4)(x^996 - 1) + (x^4 - x^2 + 1) + (x^2 - 1).

    But x^996 - 1 is divisible by x^6 + 1, and
    x^6 + 1 = (x^4 - x^2 + 1)(x^2 + 1).
    Therefore the remainder is x^2 - 1.

    ReplyDelete