Ruffini's Rule - Algorithm

Algorithm

The rule establishes a method for dividing the polynomial

by the binomial

to obtain the quotient polynomial

and a remainder s.

The algorithm is in fact the long division of P(x) by Q(x).

To divide P(x) by Q(x):

1. Take the coefficients of P(x) and write them down in order. Then write r at the bottom left edge, just over the line:

| a_n a_n-1 ... a₁ a₀ | r | ----|--------------------------------------------------------- | |

2. Pass the leftmost coefficient (a_n) to the bottom, just under the line:

| a_n a_n-1 ... a₁ a₀ | r | ----|--------------------------------------------------------- | a_n | | = b_n-1 |

3. Multiply the rightmost number under the line by r and write it over the line and one position to the right:

| a_n a_n-1 ... a₁ a₀ | r | b_n-1r ----|--------------------------------------------------------- | a_n | | = b_n-1 |

4. Add the two values just placed in the same column

| a_n a_n-1 ... a₁ a₀ | r | b_n-1r ----|--------------------------------------------------------- | a_n a_n-1+(b_n-1r) | | = b_n-1 = b_n-2 |

5. Repeat steps 3 and 4 until no numbers remain

| a_n a_n-1 ... a₁ a₀ | r | b_n-1r ... b₁r b₀r ----|--------------------------------------------------------- | a_n a_n-1+(b_n-1r) ... a₁+b₁r a₀+b₀r | | = b_n-1 = b_n-2 ... = b₀ = s |

The b values are the coefficients of the result (R(x)) polynomial, the degree of which is one less than that of P(x). The final value obtained, s, is the remainder. As shown in the polynomial remainder theorem, this remainder is equal to P(r), the value of the polynomial at r.