Ruffini's rule


In mathematics, Ruffini's rule is a practical way for paper-and-pencil computation of the Euclidean division of a polynomial by a binomial of the form. It was described by Paolo Ruffini in 1804. Ruffini's rule is a special case of synthetic division when the divisor is a linear factor.

Algorithm

The rule establishes a method for dividing the polynomial
by the binomial
to obtain the quotient polynomial
The algorithm is in fact the long division of P by Q.
To divide P by Q:
  1. Take the coefficients of P and write them down in order. Then write r at the bottom left edge, just over the line:
  2. :
  3. Pass the leftmost coefficient to the bottom, just under the line:
  4. :
  5. Multiply the rightmost number under the line by r and write it over the line and one position to the right:
  6. :
  7. Add the two values just placed in the same column
  8. :
  9. Repeat steps 3 and 4 until no numbers remain
  10. :
The b values are the coefficients of the result polynomial, the degree of which is one less than that of P. The final value obtained, s, is the remainder. The polynomial remainder theorem asserts that this remainder is equal to P, the value of the polynomial at r.

Example of use

A worked example of polynomial division, as described above.
Let:
P is going to be divided by Q using Ruffini's rule. The main problem is that Q is not a binomial of the form x − r, but rather x + r. Q must be rewritten in this way:
Now the algorithm is applied:
1. Write down the coefficients and r. Note that, as P didn't contain a coefficient for x, 0 is written:
| 2 3 0 -4
|
-1 |
----|----------------------------
|
|
2. Pass the first coefficient down:
| 2 3 0 -4
|
-1 |
----|----------------------------
| 2
|
3. Multiply the last obtained value by r:
| 2 3 0 -4
|
-1 | -2
----|----------------------------
| 2
|
4. Add the values:
| 2 3 0 -4
|
-1 | -2
----|----------------------------
| 2 1
|
5. Repeat steps 3 and 4 until it's finished:
| 2 3 0 -4
|
-1 | -2 -1 1
----|----------------------------
| 2 1 -1 -3
|
So, if original number = divisor × quotient + remainder, then

Uses of the rule

Ruffini's rule has many practical applications; most of them rely on simple division or the common extensions given still further below.

Polynomial root-finding

The rational root theorem states that for a polynomial all of whose coefficients are integers, the real rational roots are always of the form p/q, where p is an integer divisor of a0 and q is an integer divisor of an. Thus if our polynomial is
then the possible rational roots are all the integer divisors of a0 :
In any case, for monic polynomials, every rational root is an integer, and so every integer root is just a divisor of the constant term. It can be shown that this remains true for non-monic polynomials, i.e. to find the integer roots of any polynomials with integer coefficients, it suffices to check the divisors of the constant term.
So, setting r equal to each of these possible roots in turn, the polynomial will be divided by. If the resulting quotient has no remainder, a root was found.
You can choose one of the following three methods: they will all yield the same results, with the exception that only through the second method and the third method can you discover that a given root is repeated.

Method 1

Division P by the binomial. If the remainder is 0, the selected number is a root :
| +1 +2 -1 -2 | +1 +2 -1 -2
| |
+1 | +1 +3 +2 -1 | -1 -1 +2
----|---------------------------- ----|---------------------------
| +1 +3 +2 0 | +1 +1 -2 0
| +1 +2 -1 -2 | +1 +2 -1 -2
| |
+2 | +2 +8 +14 -2 | -2 0 +2
----|---------------------------- ----|---------------------------
| +1 +4 +7 +12 | +1 0 -1 0
In the example, P is a degree three polynomial. By the fundamental theorem of algebra, it can have no more than three complex solutions. Hence, the polynomial is factored as follows:

Method 2

Start just as in Method 1 until a valid root is found. Then, instead of restarting the process with the other possible roots, continue testing the possible roots against the result of the Ruffini on the valid root found currently, until only a coefficient is remaining :
| +1 +2 -1 -2 | +1 +2 -1 -2
| |
-1 | -1 -1 +2 -1 | -1 -1 +2
----|--------------------------- ----|---------------------------
| +1 +1 -2 | 0 | +1 +1 -2 | 0
| |
+2 | +2 +6 +1 | +1 +2
------------------------- -------------------------
| +1 +3 |+4 | +1 +2 | 0
|
-2 | -2
-------------------
| +1 | 0

Method 3

Thus, for each r in our set, r is actually a root of the polynomial if and only if P=0
This shows that finding integer and rational roots of a polynomial neither requires any division nor the application of Ruffini's rule.
However, once a valid root has been found, call it r1:
you can apply Ruffini's rule to determine
This allows you to partially factorize the polynomial as
Any additional root of the polynomial is also a root of Q and, of course, is still to be found among the possible roots determined earlier which have not yet been checked is not a root of Q either; more formally, P≠0 → Q.
Thus, you can proceed evaluating Q instead of P, and dividing Q by.
Even if you're only searching for roots, this allows you to evaluate polynomials of successively smaller degree, as the factorization proceeds.
If, as is often the case, you are also factorizing a polynomial of degree n, then:
Finding roots without applying Ruffini's Rule
Possible roots =
and the remainder of is 12
Possible roots =
Then, applying Ruffini's Rule:
Here, r1=-1 and
Again, applying Ruffini's Rule:
As it was possible to completely factorize the polynomial, it's clear that the last root is -2.

Polynomial factoring

Having used the "p/q" result above to find all the real rational roots of a particular polynomial, it is but a trivial step further to partially factor that polynomial using those roots. As is well-known, each linear factor which divides a given polynomial corresponds with a root r, and vice versa.
So if
By the fundamental theorem of algebra, R should be equal to P, if all the roots of P are rational. But since used method finds only rational roots, it is very likely that R is not equal to P; it is very likely that P has some irrational or complex roots not in R. So consider
If S = 1, then it is known R = P and procedure is done. Otherwise, S will itself be a polynomial; this is another factor of P which has no real rational roots. So write out the right-hand-side of the following equation in full:
One can call this a complete factorization of P over Q if S = 1. Otherwise, there exists only a partial factorization of P over Q, which may or may not be further factorable over the rationals; but which will certainly be further factorable over the reals or at worst the complex plane.

Example 1: no remainder

Let
Using the methods described above, the rational roots of P are:
Then, the product of is
And P/R:
Hence the factored polynomial is P = R · 1 = R:

Example 2: with remainder

Let
Using the methods described above, the rational roots of P are:
Then, the product of is
And P/R
As, the factored polynomial is P = R · S:

Factoring over the complexes

To completely factor a given polynomial over C, the complex numbers, all of its roots must be known. For example, consider the polynomial above:
Extracting its rational roots and factoring it, yields:
But that is not completely factored over C. If factorization of a polynomial must finish to a product of linear factors, quadratic factor must be dealt with:
The easiest way is to use quadratic formula, which yields
and the solutions
So the completely factored polynomial over C will be:
However, one cannot, in every case expect things to be so easy; the quadratic formula's analogue for fourth-order polynomials is very convoluted and no such analogue exists for 5th-or-higher order polynomials. See Galois theory for a theoretical explanation of why this is so, and see numerical analysis for ways to approximate roots of polynomials numerically.

Limitations

It is entirely possible that, when looking for a given polynomial's roots, one might obtain a intricate higher-order polynomial for S which is further factorable over the rationals even before considering irrational or complex factorings. Consider the polynomial x5 − 3x4 + 3x3 − 9x2 + 2x − 6. Using Ruffini's method only one root is found ; factoring it out to: P =.
As explained above, if stated assignment was to "factor into irreducibles over C", it would be necessary to find some way to dissect the quartic and look for its irrational and/or complex roots. But if the assignment were "factor into irreducibles over Q", one might think it is already done; but it is important to realize that this might not necessarily be the case.
For in this instance the quartic is actually factorable as the product of two quadratics. These, at last, are irreducible over the rationals ; which concludes the method; P =. In this instance it is in fact easy to factor our quartic by treating it as a biquadratic equation; but finding such factorings of a higher degree polynomial can be very difficult.

History

This method was invented by Paolo Ruffini. He took part in a competition organised by the Italian Scientific Society. The question to be answered was a method to find the roots of any polynomial. Five submissions were received. In 1804 Ruffini's was awarded the first place and the method was published. Ruffini published refinements of the method in 1807 and 1813.
Horner's method was published in 1819 and in a refined version in 1845.