Let us consider a special case of the division of polynomials – the division of a polynomial by a binomial of the form x - b₀. The division algorithm for this case is called Horner's scheme or the abbreviated method of dividing a polynomial by a binomial. Let it be required to divide a polynomial
by the binomial b(x) = x - b₀, b(x)=x-b₀, that is, it is required to represent the polynomial a(x) in the form
a(x)=b(x)*c(x) + r(x), where the degree of the quotient c(x) is equal to n-1, and the degree of the remainder r(x) is equal to 0. Let
That is We multiply x-b₀ and c(x), add it to r₀ and equate the coefficients of the polynomials with the same powers of x on the left and right sides of the equality:
a₀=c₁,
a₁=c₂ - c₁*b₀,
...
a_n-2=c_n-1 - c_n-2*b₀,
a_n-1=c_n - c_n-1*b₀,
a_n=r₀ - c_n*b₀,

From these equalities we obtain recurrent formulas for determining the values ​​of c_i and the remainder r₀.
c₁=a₀,
c₂=a₁ + c₁*b₀,
...
c_n-1=a_n-2 + c_n-2*b₀,
c_n=a_n-1 + c_n-1*b₀,
r₀=a₀ + c_n*b₀.

For the convenience of calculations using these formulas, a table is created that is filled in from left to right.
The first line contains the coefficients of the dividend in descending order of powers of x and the number b₀.
The second line contains the corresponding values of expressions _i*b₀ (the first number is 0, since c₀=0).
The numbers in the first row are added to the numbers in the second row and written to the third row. As a result, in the third row we get the coefficients of the quotient, and the last number is the remainder.



We fill in this table in this order:

First, we fill in the first line. Under the first number of the first line we write 0.

We add the numbers in the first column, and the result will be the first number in the third row.

Then the first number of the third row c₁ is multiplied by the last number of the first row b₀, the result is written to the second place of the second row.

We add up the numbers of the second column and get the second number of the third row c₂.

We multiply this number again by the last number of the first row b₀, and write the result in third place in the second row.

We add up the numbers in the third column and get the third number in the third row, and so on.

Although the explanation looks rather cumbersome, it is very simple and convenient to perform division using Horner's scheme. Let's consider the application of Horner's scheme using examples.

Example 1.
Divide the polynomial x⁴ - 3x³ - 3x² + 7x + 6 by the binomial x-3 using Horner's scheme.
Solution.
The dividend a(x)=x⁴ - 3x³ - 3x² + 7x + 6, b₀=3. In accordance with Horner's scheme, we fill in the table


Thus, the remainder r (the last number in the third row) is zero. This means that the polynomial x⁴ - 3x³ - 3x² + 7x + 6 is completely divisible by x - 3. Quotient (x)=1*x³ + 0*x² - 3x - 2.
Answer: x⁴ - 3x³ - 3x² + 7x + 6=(x³ - 3x - 2)*(x - 3).

Example 2.
Divide the polynomial 2x⁵ + 5x⁴ - 4x³ + 612 by the binomial x + 4 using Horner's scheme.
Solution.
The dividend a(x)= 2x⁵ + 5x⁴ - 4x³ + 612, b₀=-4. In accordance with Horner's scheme, we fill in the table


The remainder r = 100 - this is the last number in the third row. The quotient (x)=2*x⁴ - 3*x³ - 8*x² - 32*x + 128.
Answer: 2x⁵ + 5x⁴ - 4x³ + 612 = (2x⁴ - 3x³ - 8x² - 32x + 128)*(x + 4) + 100.


The division of a polynomial a(x) by a binomial of the form b₁x - b₀ is easily reduced to the case of division by x - b₀.
Let a(x) = (b₁x - b₀)*c(x) + r₀, we transform this expression as follows:


An analysis of the last expression shows that the remainder of a(x) divided by b₁x - b₀ is the same as the remainder of a(x) divided by x - b₀/b₁, and the coefficients of the quotient c(x) are obtained from the coefficients of the quotient from division by x - b₀/b₁ by dividing them by b₁.

Example 3.
Divide the polynomial x³ - 6x² + 5x + 2 by the binomial 2x + 1 using Horner's scheme.
Solution.
Since 2x + 1=2(x + 1/2), using Horner's scheme we will divide the original polynomial by x+1/2, then divide the resulting coefficients of the quotient by 2.


The remainder r₀ = -17/8. The coefficients of the quotient are obtained by dividing the coefficients in the third row of the table by 2. Thus, the quotient of dividing the original polynomial by 2x + 1


Answer:

Example 4.
Divide the polynomial x⁵ - x³ + 2x - 1 by the binomial 3 - 2x using Horner's scheme.
Solution.
Since 3 - 2x = - 2(x - 3/2), using Horner's scheme we will divide the original polynomial by x - 3/2, then we divide the obtained quotient coefficients by -2.


The remainder r₀ = 199/32. The coefficients of the quotient are obtained by dividing the coefficients in the third row of the table by -2. Thus, the quotient of dividing the original polynomial by 3 - 2x

Answer:

Using the Horner's scheme to decompose a polynomial by powers of a binomial

Let us consider another application of Horner's scheme – decomposition of a polynomial by powers of a binomial. For any polynomial where a₀ ≠ 0, n ≥ 1, and for any number b₀ we can write the decomposition of a(x) by powers x - b₀:
As can be seen from this formula, in order to calculate p_n, it is necessary to divide the polynomial a(x) by x - b₀ and find the remainder r = p_n. In the quotient, we get the polynomial


Now, to calculate p_n-1, you need to divide the polynomial d₁ (x) by x - b₀ and find the remainder r=p_n-1. In the quotient we get the polynomial


Then we continue dividing until the quotient is a number. The remainder obtained in the last step will be equal to p₁, and the quotient d_n=p₀.
At each step, division by x-b₀ will be carried out using Horner's scheme. It is very convenient to write down the calculation results in one common table. Let's consider the corresponding example.

Example 5.
Decompose the polynomial 2x⁴ + x³ - 5x + 3 by the powers of the binomial x + 1.
Solution.
We will perform all calculations by sequentially filling in the table according to the algorithm.
Thus, we obtain that the remainder of the division of the original polynomial by x+1 is 9, the coefficients of the quotient are 2,-7,9,-10.

Answer: 2x⁴ + x³ - 5x + 3 = 2(x + 1)⁴ - 7(x + 1)³ + 9(x + 1)² - 10(x + 1) + 9.

Calculating the value of a polynomial at a given point using Horner's scheme

Another problem that can be solved using Horner's scheme is calculating the value of a polynomial at a given point. Let the polynomial a(x) be divisible by the binomial x-b₀ with remainder r₀. That is


If we substitute the value x=b₀ into this equality, we get a(b₀)=r₀. Thus, we have proved Bezout's theorem.

Bezout's theorem. If x₀ is an arbitrary number, then dividing the polynomial a(x) by the binomial x-x₀ results in a remainder equal to the value of the polynomial for x=x₀, that is r₀= a(x₀).

Thus, using Horner's scheme, one can find the value of a polynomial for a given value x=x₀ as the remainder of dividing this polynomial by the binomial x-x₀. Sometimes this is much easier to do than substituting x₀ into the original polynomial.

Bezout's theorem has a very important consequence.

Consequence. A number x₀ is a root of a polynomial a(x) if and only if the polynomial a(x) is divisible by the binomial x-x₀.

This consequenc allows us to check whether a number x₀ is a root of a polynomial by calculating the remainder of the division of the polynomial by the binomial x-x₀.

Example 6.
Calculate the value of a polynomial 2x⁶ + 6x⁵ + x⁴ - 4x³ + 3x² - x - 1 at x=-3.
Solution.
Calculating the value of a polynomial at x=-3 is equivalent to finding the remainder when dividing this polynomial by x+3. To do this, we will use Horner's scheme

The remainder r (this is the last number in the third line) is 218.
The quotient (x)=2x⁵ + x³ - 7x² + 24x - 73.
2x⁶ + 6x⁵ + x⁴ - 4x³ + 3x² - x - 1=(2x⁵ + x³ - 7x² + 24x - 73)*(x+3)+218.
Answer: 218.