Devise an algorithm which, for any polynomial P(x), will determine the polynomial remainder of P(x)/(x^2+x+1) without actually performing the division.

We know
Dividend = Divisor*Quotient+Remainder
Here Dividend Polynomial=P(x)
But Divisor Polynomial is choosen as
D(x): x³-1 = (x-1)*(x²+x+1)
To get Remainder when divided by x³-1, we can replace
x³ with 1 in the polynomial P(x).
This is same as adding all the coefficients of degree of
forms 3k,3k+1,3k+2.Let them be a(0),a(1) and a(2) respectively
Now we will have 3 coefficients in all for the remainder
polynomial, but this is when divided by x³-1
Now subtract a(2) from a(0) and a(1)
Now the remainder polynomial when P(x) divided by 
x²+x+1 will be (a(1)-a(2))x+a(0)-a(2).

Posted by Praneeth on 2008-04-22 07:55:47