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.

(In reply to Manipulate by brianjn)

Let a, b, c, .............X, Y, Z be the coefficients of the descending powers of P(x).

Divide the coefficients by the coefficients of x^2+x+1, ie 1, 1, 1.  We can ignore the "x" symbol for this process.
                         a   -b+a            
1 1 1 | a      b       c       d ...........
           a      a       a
               -a+b  -a+c     d
               -a+b  -a+b   -a+b
                        -b+c  a-b+d  e
                
A little later down the division the following terms appear:
-a+b-d+e-g+h   -a+c-d+f-g+i  j

Looking at the first two of these in the context of the descending coefficients,

             a    b    c    d    e    f    g    h    i,

there is a distinct pattern in the signage of these values, as indicated by the formatting, in those terms.

In general all powers are assigned a coefficient [zero if that power is not represented in P(x)].
Then, beginning with the first coefficient on the right proceed to add (with due respect to the positive or negative value) every third coefficient as you proceed left; these are bold in my example.  Call this sum, TotalA.

Go to the third coeffient from the right (italics) and similarly add to it every coefficient as you step left by three.  Call this TotalB. 
 That leaves those beginning with the second coefficient from the right, and its subsequent set to be similarly treated.  Call this sum TotalC.

The remainder of the division is given by:
        (TotalC - TotalB) * x + (TotalA - TotalB)

Posted by brianjn on 2008-04-16 20:21:00