In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, Ruffini's rule is a method for
computation
A computation is any type of arithmetic or non-arithmetic calculation that is well-defined. Common examples of computation are mathematical equation solving and the execution of computer algorithms.
Mechanical or electronic devices (or, hist ...
of the
Euclidean division
In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
of a
polynomial
In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
by a
binomial of the form ''x – r''. It was described by
Paolo Ruffini in 1809.
The rule is a special case of
synthetic division in which the
divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a '' multiple'' of m. An integer n is divisible or evenly divisibl ...
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''(''x'') by ''Q''(''x'').
To divide ''P''(''x'') by ''Q''(''x''):
# Take the coefficients of ''P''(''x'') and write them down in order. Then, write ''r'' at the bottom-left edge just over the line:
#:
# Pass the leftmost coefficient (''a''
''n'') to the bottom just under the line.
#:
# Multiply the rightmost number under the line by ''r'', and write it over the line and one position to the right.
#:
# Add the two values just placed in the same column.
#:
# Repeat steps 3 and 4 until no numbers remain.
#:
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 an example of polynomial division as described above.
Let:
:
:
''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
:
Now the algorithm is applied:
- 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 , ,
----, --------------------, -------
, ,
, ,
- Pass the first coefficient down:
, 2 3 0 , -4
, ,
-1 , ,
----, --------------------, -------
, 2 ,
, ,
- Multiply the last obtained value by ''r'':
, 2 3 0 , -4
, ,
-1 , -2 ,
----, --------------------, -------
, 2 ,
, ,
- Add the values:
, 2 3 0 , -4
, ,
-1 , -2 ,
----, --------------------, -------
, 2 1 ,
, ,
- 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
:
, where
:
and
Application to polynomial factorization
Ruffini's rule can be used when one needs the quotient of a polynomial by a binomial of the form
(When one needs only the remainder, the
polynomial remainder theorem provides a simpler method.)
A typical example, where one needs the quotient, is the
factorization of a polynomial
for which one knows a root :
The remainder of the
Euclidean division
In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
of
by is , and, if the quotient is
the Euclidean division is written as
:
This gives a (possibly partial) factorization of
which can be computed with Ruffini's rule. Then,
can be further factored by factoring
The
fundamental theorem of algebra states that every polynomial of positive degree has at least one
complex
Complex commonly refers to:
* Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe
** Complex system, a system composed of many components which may interact with each ...
root. The above process shows the fundamental theorem of algebra implies that every polynomial can be factored as
:
where
are complex numbers.
History
The method was invented by
Paolo Ruffini, who took part in a competition organized by the Italian Scientific Society (of Forty). The challenge was to devise 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. He later published refinements of his work in 1807 and again in 1813.
See also
*
Lill's method, doing the division graphically
*
Horner's method
References
External links
*
* {{commons category-inline
Polynomials
Root-finding algorithms
Division (mathematics)