Editing Ruffini's rule

{{Short description|Polynomial division computation method}}
In [[mathematics]], '''Ruffini's rule''' is a method for  [[computation]] of the [[Euclidean division]] of a [[polynomial]] by a [[Binomial (polynomial)|binomial]] of the form ''x – r''. It was described by [[Paolo Ruffini (mathematician)|Paolo Ruffini]] in 1809.<ref>{{cite journal|last1=Cajori|first1=Florian|year=1911|title=Horner's method of approximation anticipated by Ruffini|url=http://projecteuclid.org/download/pdf_1/euclid.bams/1183421253|format=PDF|journal=[[Bulletin of the American Mathematical Society]]|volume=17|issue=8|pages=389–444|doi=10.1090/s0002-9904-1911-02072-9|doi-access=free|author-link1=Florian Cajori}}</ref> 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:
:<math>P(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0</math>
by the binomial:
:<math>Q(x)=x-r</math>
to obtain the quotient polynomial:
:<math>R(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\cdots+b_1x+b_0.</math>

The algorithm is in fact the [[polynomial long division|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:
#:<math>
\begin{array}{c|c c c c|c}
 & a_n & a_{n-1} & \dots & a_1 & a_0\\
r & & & & & \\
\hline
 & & & & & \\
\end{array}
</math>
# Pass the leftmost coefficient (''a''<sub>''n''</sub>) to the bottom just under the line.
#:<math>
\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}
</math>
# Multiply the rightmost number under the line by ''r'', and write it over the line and one position to the right.
#:<math>
\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}
</math>
# Add the two values just placed in the same column.
#:<math>
\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}
</math>
# Repeat steps 3 and 4 until no numbers remain.
#:<math>
\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 & =s \\
\end{array}
</math>

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:
<!-- The \,\! is to keep the formulae rendered as PNG instead of HTML to ensure consistency of representation. Please don't remove it.--> 
:<math>P(x)=2x^3+3x^2-4\,\!</math>
:<math>Q(x)=x+1.\,\!</math>

''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
:<math>Q(x)=x+1=x-(-1).\,\!</math>
Now the algorithm is applied:
<ol>
<li>Write down the coefficients and ''r''. Note that, as ''P''(''x'') didn't contain a coefficient for ''x'', 0 is written:
<pre>
     |     2     3     0  |  -4
     |                    |               
  -1 |                    |               
 ----|--------------------|-------
     |                    |               
     |                    |               
</pre>
</li>
<li>Pass the first coefficient down:
<pre>
     |     2     3     0  |  -4
     |                    |               
  -1 |                    |               
 ----|--------------------|-------
     |     2              |               
     |                    |               
</pre>
</li>
<li>Multiply the last obtained value by ''r'':
<pre>
     |     2     3     0  |  -4
     |                    |               
  -1 |          -2        |                
 ----|--------------------|-------
     |     2              |               
     |                    |               
</pre>
</li>
<li>Add the values:
<pre>
     |     2     3     0  |  -4
     |                    |
  -1 |          -2        |
 ----|--------------------|-------
     |     2     1        |
     |                    |               
</pre>
</li>
<li>Repeat steps 3 and 4 until it's finished:
<pre>
     |     2     3     0   | -4
     |                     |
  -1 |          -2    -1   |  1
 ----|----------------------------
     |     2     1    -1   | -3
     |{result coefficients}|{remainder}
</pre>
</li>
</ol>
<!-- The \,\! is to keep the formulae rendered as PNG instead of HTML to ensure consistency of representation. Please don't remove it.-->

So, if ''original number'' = ''divisor'' × ''quotient'' + ''remainder'', then
:<math>P(x)=Q(x)R(x)+s\,\!</math>, where

:<math>R(x) = 2x^2+x-1\,\!</math> and <math>s=-3; \quad \Rightarrow 2x^3+3x^2-4 = (2x^2+x-1)(x+1) - 3\!</math>

==Application to polynomial factorization==
Ruffini's rule can be used when one needs the quotient of a polynomial {{mvar|P}} by a binomial of the form <math>x-r.</math> (When one needs only the remainder, the [[polynomial remainder theorem]] provides a simpler method.)

A typical example, where one needs the quotient, is the [[polynomial factorization|factorization]] of a polynomial <math>p(x)</math> for  which one knows a root {{mvar|r}}:

The remainder of the [[Euclidean division]] of <math>p(x)</math> by {{mvar|r}} is {{math|0}}, and, if the quotient is <math>q(x),</math> the Euclidean division is written as
:<math>p(x)=q(x)\,(x-r).</math>

This gives a (possibly partial) factorization of <math>p(x),</math> which can be computed with Ruffini's rule. Then, <math>p(x)</math> can be further factored by factoring <math>q(x).</math>

The [[fundamental theorem of algebra]] states that every polynomial of positive degree has at least one [[complex number|complex]] root. The above process shows the fundamental theorem of algebra implies that every polynomial {{math|1=''p''(''x'') = ''a''<sub>''n''</sub>''x''<sup>''n''</sup> + ''a''<sub>''n''−1</sub>''x''<sup>''n''−1</sup> + ⋯ + ''a''<sub>1</sub>''x'' + ''a''<sub>0</sub>}} can be factored as 
:<math>p(x)=a_n(x-r_1)\cdots(x-r_n),</math>
where <math>r_1,\ldots,r_n</math> are complex numbers.

==History==
The method was invented by [[Paolo Ruffini (mathematician)|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==
<references/>

==External links==
* {{MathWorld|SyntheticDivision|Ruffini's rule}}
* {{commons category-inline}}

[[Category:Polynomials]]
[[Category:Root-finding algorithms]]
[[Category:Division (mathematics)]]