Деление многочленов: алгоритмы и методы

Algorithm for division of polynomials
a shorthand version of this method
In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree, a generalized version of the familiar arithmetic technique called long division. It can be done easily by hand, because it separates an otherwise complex division problem into smaller ones. Sometimes using a shorthand version called synthetic division is faster, with less writing and fewer calculations. Another abbreviated method is polynomial short division (Blomqvist's method). Polynomial long division is an algorithm that implements the Euclidean division of polynomials, which starting from two polynomials A (the dividend) and B (the divisor) produces, if B is not zero, a quotient Q and a remainder R such that
A = BQ + R,
and either R = 0 or the degree of R is lower than the degree of B. These conditions uniquely define Q and R, which means that Q and R do not depend on the method used to compute them. The result R = 0 occurs if and only if the polynomial A has B as a factor. Thus long division is a means for testing whether one polynomial has another as a factor, and, if it does, for factoring it out. For example, if a root r of A is known, it can be factored out by dividing A by (x – r).

Blomqvist's method is an abbreviated version of the long division above. This pen and paper method uses the same algorithm as polynomial long division, but mental calculation is used to determine remainders. This requires less writing, and can therefore be a faster method once mastered. The division is at first written in a similar way as long multiplication with the dividend at the top, and the divisor below it. The quotient is to be written below the bar from left to right. Divide the first term of the dividend by the highest term of the divisor (x3 ÷ x = x2). Place the result below the bar. x3 has been divided leaving no remainder, and can therefore be marked as used with a backslash. The result x2 is then multiplied by the second term in the divisor −3 = −3x2. Determine the partial remainder by subtracting −2x2 − (−3x2) = x2. Mark −2x2 as used and place the new remainder x2 above it. Divide the highest term of the remainder by the highest term of the divisor (x2 ÷ x = x). Place the result (+x) below the bar. x2 has been divided leaving no remainder, and can therefore be marked as used. The result x is then multiplied by the second term in the divisor −3 = −3x. Determine the partial remainder by subtracting 0x − (−3x) = 3x. Mark 0x as used and place the new remainder 3x above it. Divide the highest term of the remainder by the highest term of the divisor (3x ÷ x = 3). Place the result (+3) below the bar. 3x has been divided leaving no remainder, and can therefore be marked as used. The result 3 is then multiplied by the second term in the divisor −3 = −9. Determine the partial remainder by subtracting −4 − (−9) = 5. Mark −4 as used and place the new remainder 5 above it. The polynomial below the bar is the quotient q(x), and the number left over (5) is the remainder r(x).

Sometimes one or more roots of a polynomial are known, perhaps having been found using the rational root theorem. If one root r of a polynomial P(x) of degree n is known then polynomial long division can be used to factor P(x) into the form (x − r)Q(x) where Q(x) is a polynomial of degree n − 1. Q(x) is simply the quotient obtained from the division process; since r is known to be a root of P(x), it is known that the remainder must be zero. Likewise, if several roots r, s, . of P(x) are known, a linear factor (x − r) can be divided out to obtain Q(x), and then (x − s) can be divided out of Q(x), etc. Alternatively, the quadratic factor can be divided out of P(x) to obtain a quotient of degree n − 2. This method is especially useful for cubic polynomials, and sometimes all the roots of a higher degree polynomial can be obtained. For example, if the rational root theorem produces a single (rational) root of a quintic polynomial, it can be factored out to obtain a quartic (fourth degree) quotient; the explicit formula for the roots of a quartic polynomial can then be used to find the other four roots of the quintic. There is, however, no general way to solve a quintic by purely algebraic methods, see Abel–Ruffini theorem.

Polynomial long division can be used to find the equation of the line that is tangent to the graph of the function defined by the polynomial P(x) at a particular point If R(x) is the remainder of the division of P(x) by (x – r)2, then the equation of the tangent line at to the graph of the function is regardless of whether or not r is a root of the polynomial.

A cyclic redundancy check uses the remainder of polynomial division to detect errors in transmitted messages.