Ruffini's rule

This article's tone or style may not reflect the encyclopedic tone used on Wikipedia. See Wikipedia's guide to writing better articles for suggestions. (February 2020) (Learn how and when to remove this template message)

In mathematics, Ruffini's rule is a method for paper-and-pencil computation of the Euclidean division of a polynomial by a binomial of the form x – r. It was described by Paolo Ruffini in 1804.^[1] The rule is a special case of synthetic division in which the divisor is a linear factor.

Algorithm[]

The rule establishes a method for dividing the polynomial

${\displaystyle P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}$

by the binomial

${\displaystyle Q(x)=x-r}$

to obtain the quotient polynomial

${\displaystyle R(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\cdots +b_{1}x+b_{0}.}$

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:

   ${\displaystyle {\begin{array}{c|c c c c|c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&&&&\\\hline &&&&&\\\end{array}}}$

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

   ${\displaystyle {\begin{array}{c|c c c c|c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&&&&\\\hline &a_{n}&&&&\\&=b_{n-1}&&&&\end{array}}}$

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

   ${\displaystyle {\begin{array}{c|c c c c|c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&b_{n-1}\cdot r&&&\\\hline &a_{n}&&&&\\&=b_{n-1}&&&&\end{array}}}$

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

   ${\displaystyle {\begin{array}{c|c c c c|c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&b_{n-1}\cdot r&&&\\\hline &a_{n}&b_{n-1}\cdot r+a_{n-1}&&&\\&=b_{n-1}&=b_{n-2}&&&\end{array}}}$

5. Repeat steps 3 and 4 until no numbers remain.

   ${\displaystyle {\begin{array}{c|c c c c|c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&b_{n-1}\cdot r&\dots &b_{1}\cdot r&b_{0}\cdot r\\\hline &a_{n}&b_{n-1}\cdot r+a_{n-1}&\dots &b_{1}\cdot r+a_{1}&a_{0}+b_{0}\cdot r\\&=b_{n-1}&=b_{n-2}&\dots &=b_{0}&=R\\\end{array}}}$

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. The polynomial remainder theorem asserts that the remainder is equal to P(r), the value of the polynomial at r.

Example[]

Here is a worked example of polynomial division as described above.

Let:

${\displaystyle P(x)=2x^{3}+3x^{2}-4\,\!}$

${\displaystyle Q(x)=x+1.\,\!}$

P(x) will be divided by Q(x) using Ruffini's rule. The main problem is that Q(x) is not a binomial of the form x − r, but rather x + r. Q(x) must be rewritten as

${\displaystyle Q(x)=x+1=x-(-1).\,\!}$

Now the algorithm is applied:

1. Write down the coefficients and r. Note that, as P(x) 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
        |{result coefficients}|{remainder}
   

So, if original number = divisor × quotient + remainder, then

${\displaystyle P(x)=Q(x)R(x)+s\,\!}$, where

${\displaystyle R(x)=2x^{2}+x-1\,\!}$ and ${\displaystyle s=-3;\quad \Rightarrow 2x^{3}+3x^{2}-4=(2x^{2}+x-1)(x+1)-3\!}$

Uses[]

Ruffini's rule has many practical applications, most of which rely on simple division (as demonstrated below) or the common extensions given still further below.

Polynomial root-finding[]

The rational root theorem states that for a polynomial f(x) = a_nxⁿ + a_n−1xⁿ⁻¹ + ⋯ + a₁x + a₀ all of whose coefficients (a_n through a₀) are integers, the real rational roots are always of the form p/q, where p is an integer divisor of a₀ and q is an integer divisor of a_n. Thus if our polynomial is

${\displaystyle P(x)=x^{3}+2x^{2}-x-2=0\,\!,}$

the possible rational roots are all the integer divisors of a₀ (−2):

${\displaystyle {\text{Possible roots:}}\left\{+1,-1,+2,-2\right\}.}$

(The example is simple because the polynomial is monic (a_n = 1). For non-monic polynomials, the set of possible roots will include some fractions but only a finite number of them since a_n and a₀ have only a finite number of integer divisors each.) 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 (a₀). It can be shown that to remain true for non-monic polynomials: to find the integer roots of any polynomials with integer coefficients, checking the divisors of the constant term suffices.

Therefore, setting r equal to each of the possible roots, in turn, the polynomial is divided by (x − r). If the resulting quotient has no remainder, a root was found.

Any of the following three methods can be chosen since all of them yield the same results, with the exception that only through the second method and the third method (when applying Ruffini's rule to obtain a factorization) can discover if a given root is repeated. (Neither method will discover irrational or complex roots.)

Method 1[]

Division P(x) by the binomial (x − each possible root). If the remainder is 0, the selected number is a root (and vice versa):

    |    +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

${\displaystyle {\begin{cases}x_{1}=+1\\x_{2}=-1\\x_{3}=-2\end{cases}}}$

In the example, P(x) 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:

${\displaystyle P(x)=(x-x_{1})(x-x_{2})(x-x_{3})=(x-1)(x+1)(x+2)=x^{3}+2x^{2}-x-2.}$

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 remains (remember that roots can be repeated: if you get stuck, try each valid root twice):

    |    +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

${\displaystyle {\begin{cases}x_{1}=-1\\x_{2}=+1\\x_{3}=-2\end{cases}}}$Method 3

• Determine the set of the possible integer or rational roots of the polynomial according to the rational root theorem.
• For each possible root r, instead of performing the division P(x)/(x–r), apply the polynomial remainder theorem, which states that the remainder of the division is P(r), the polynomial evaluated for x = r. Thus, for each r in our set, r is a root of the polynomial if and only if P(r)=0 That shows that finding integer and rational roots of a polynomial no division or the application of Ruffini's rule. However, once a valid root has been found, call it r₁: Ruffini's rule can be applied to determine Q(x) = P(x) / (x – r₁). That allows a partial factorization of the polynomial as P(x) = (x – r₁) · Q(x) Any additional (rational) root of the polynomial is also a root of Q(x) and, of course, is still to be found among the possible roots determined earlier, which have not yet been checked (any value already determined not to be a root of P(x) is not a root of Q(x) either; more formally, P(r)≠0 → Q(r)≠0). Thus, you can proceed evaluating Q(r) instead of P(r), and (as long as you can find another root, r₂) dividing Q(r) by (x–r₂). Even if you search only for roots, that allows you to evaluate polynomials of successively-smaller degrees as the factorization proceeds. If, as is often the case, you are also factorizing a polynomial of degree n:
• if you have found p=n rational solutions you end up with a complete factorization (see below) into p=n linear factors;
• if you have found p<n rational solutions you end up with a partial factorization (see below) into p linear factors and another non-linear factor of degree n–p, which, in turn, may have irrational or complex roots.

Examples[]

Finding roots without applying Ruffini's Rule[]

P(x) = x³ + 2x² – x – 2

Possible roots = {1, –1, 2, −2}

• P(1) = 0 → x₁ = 1
• P(−1) = 0 → x₂ = −1
• P(2) = 12 → 2 is not a root of the polynomial

and the remainder of (x³ + 2x² − x − 2) / (x − 2) is 12

• P(−2) = 0 → x₃ = -2

Finding roots applying Ruffini's Rule and obtaining a (complete) factorization[]

P(x) = x³ + 2x² − x − 2

Possible roots = {1, −1, 2, −2}

• P(1) = 0 → x₁ = 1

Then, applying Ruffini's Rule:

(x³ + 2x² − x − 2) / (x − 1) = x² + 3x + 2

x³ + 2x² − x − 2 = (x − 1)(x² + 3x + 2)

Here, r₁=−1 and Q(x) = x² + 3x + 2

• Q(−1) = 0 → x₂ = −1

Again, applying Ruffini's Rule:

(x² + 3x + 2) / (x + 1) = x + 2

x³ + 2x² − x − 2 = (x − 1)(x² + 3x + 2) = (x − 1)(x + 1)(x + 2)

As it was possible to completely factorize the polynomial, it's clear that the last root is −2 (the previous procedure would have given the same result, with a final quotient of 1).

Polynomial factoring[]

Having used the "p/q" result above (or, to be fair, any other means) 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 (x − r), which divides a given polynomial corresponds with a root r and vice versa.

So if

${\displaystyle P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}\,\!}$ is our polynomial; and

${\displaystyle R=\left\{{\mbox{roots of }}P(x)\in \mathbb {Q} \right\}\,\!}$ are the found roots, then consider the product

${\displaystyle R(x)=a_{n}{\prod (x-r)}{\mbox{ for all }}r\in R.\,\!}$

By the fundamental theorem of algebra, R(x) should be equal to P(x), if all the roots of P(x) are rational. However, since the method finds only rational roots, it is very likely that R(x) is not equal to P(x); it is very likely that P(x) has some irrational or complex roots not in R. So consider

${\displaystyle S(x)={\frac {P(x)}{R(x)}}\,\!}$, which can be calculated using polynomial long division.

If S(x) = 1, then it is known R(x) = P(x) and procedure is done. Otherwise, S(x) will itself be a polynomial, which is another factor of P(x), which has no real rational roots. Therefore, write out the right-hand-side of the following equation in full:

${\displaystyle P(x)=R(x)\cdot S(x).\,\!}$

One can call it a complete factorization of P(x) over Q (the rationals) if S(x) = 1. Otherwise, there is only a partial factorization of P(x) over Q, which may or may not be further factorable over the rationals but will certainly be further factorable over the reals or at worst the complex plane. (Note that a "complete factorization" of P(x) over Q means a factorization as a product of polynomials with rational coefficients, such that each factor is irreducible over Q, answer "irreducible over Q" means that the factor cannot be written as the product of two non-constant polynomials with rational coefficients and smaller degree.)

Example 1: no remainder[]

Let

${\displaystyle P(x)=x^{3}+2x^{2}-x-2.\,\!}$

Using the methods described above, the rational roots of P(x) are:

${\displaystyle R=\left\{+1,-1,-2\right\}.\,\!}$

Then, the product of (x − each root) is

${\displaystyle R(x)=1(x-1)(x+1)(x+2).\,\!}$

And P(x)/R(x):

${\displaystyle S(x)=1.\,\!}$

Hence the factored polynomial is P(x) = R(x) · 1 = R(x):

${\displaystyle P(x)=(x-1)(x+1)(x+2).\,\!}$

Example 2: with remainder[]

Let

${\displaystyle P(x)=2x^{4}-3x^{3}+x^{2}-2x-8.\,\!}$

Using the methods described above, the rational roots of P(x) are:

${\displaystyle R=\left\{-1,+2\right\}.\,\!}$

Then, the product of (x − each root) is

${\displaystyle R(x)=(x+1)(x-2).\,\!}$

And P(x)/R(x)

${\displaystyle S(x)=2x^{2}-x+4.\,\!}$

As ${\displaystyle S(x){\neq }1}$, the factored polynomial is P(x) = R(x) · S(x):

${\displaystyle P(x)=(x+1)(x-2)(2x^{2}-x+4).\,\!}$

Factoring over the complexes[]

To completely factor a given polynomial over C, the complex numbers, all of its roots must be known (and that could include irrational and/or complex numbers). For example, consider the polynomial above:

${\displaystyle P(x)=2x^{4}-3x^{3}+x^{2}-2x-8.\,\!}$

Extracting its rational roots and factoring it, yields:

${\displaystyle P(x)=(x+1)(x-2)(2x^{2}-x+4).\,\!}$

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:

${\displaystyle 2x^{2}-x+4=0.\,\!}$

The easiest way is to use quadratic formula, which yields

${\displaystyle x={\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}={\frac {1\pm {\sqrt {(-1)^{2}-4\cdot 2\cdot 4}}}{2\cdot 2}}={\frac {1\pm {\sqrt {-31}}}{4}}\,\!}$

and the solutions

${\displaystyle x_{1}={\frac {1+{\sqrt {-31}}}{4}}\,\!}$

${\displaystyle x_{2}={\frac {1-{\sqrt {-31}}}{4}}.\,\!}$

So the completely factored polynomial over C will be:

${\displaystyle P(x)=2(x+1)(x-2)\left(x-{\frac {1+i{\sqrt {31}}}{4}}\right)\left(x-{\frac {1-i{\sqrt {31}}}{4}}\right).\,\!}$

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 fifth-order or higher polynomials. See Galois theory for a theoretical explanation of why that is so, and see numerical analysis for ways to approximate roots of polynomials numerically.

Limitations[]

That may be looking for a given polynomial's roots, an intricate higher-order polynomial for S(x) is obtained, which is further factorable over the rationals even before irrational or complex factors are considered such as for the polynomial x⁵ − 3x⁴ + 3x³ − 9x² + 2x − 6. Using Ruffini's method, only one root is found (x = 3), factoring it out to P(x) = (x⁴ + 3x² + 2)(x − 3).

As explained above, if the 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 might not be the case.

In that instance, the quartic is factorable as the product of two quadratics (x² + 1)(x² + 2). They, at last, are irreducible over the rationals (and the reals as well in that example), which concludes the method; P(x) = (x² + 1)(x² + 2)(x − 3). In that instance, it is easy to factor the quartic by treating it as a biquadratic equation; but finding such factors of a higher degree polynomial can be very difficult.

History[]

The method was invented by Paolo Ruffini, who took part in a competition organized by the Italian Scientific Society (of Forty). 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 first place, and his method was published. Ruffini published refinements of his method in 1807 and 1813.

Horner's method was published in 1819 and a refined version in 1845.

See also[]

• Lill's method, doing the division graphically
• Horner's method
• Polynomial long division

References[]

External links[]

• Weisstein, Eric W. "Ruffini's rule". MathWorld.
• Media related to Ruffini's rule at Wikimedia Commons