Main Index Algebraic structures Polynomial rings Univariate polynomials
 Subject Index
comment on the page

Division of Polynomials

The classical algorithm for dividing one polynomial by another one is based on the so-called long division algorithm which  basis is formed by the following result.

Division algorithm for polynomials: Let typeset structure be a field. If typeset structure and typeset structure are polynomials in typeset structure, with typeset structure 1, there exist unique polynomials typeset structure and typeset structure such that typeset structure and typeset structure.

It is customary to call typeset structure (polynomial) quotient and typeset structure the (polynomial) remainder.

We shall prove this result because the given proof is constructive and provides a hint how to realize the long division.

Let

a(x) = a _ n x^n + a _ (n - 1) x^(n - 1) + ... + a _ 0,     a _ n != 0,

b(x) = b _ m x^m + b _ (m - 1) x^(m - 1) + ... + b _ 0,     b _ m != 0.

If typeset structure the result is obvious because it is sufficient to take typeset structure and typeset structure. So let us assume that typeset structure. Since typeset structure is a field, every non-zero element has its multiplicative inverse in typeset structure,  especially there exists typeset structure. Consider the polynomials

q _ 1(x)= a _ n b _ m^(-1) x^(n - m),

r _ 1(x)= f(x) - q _ 1(x) q(x) .

Obviously, typeset structure. If typeset structure the procedure ends. Suppose therefore that typeset structure. If we denote by typeset structure the leading coefficient of polynomial typeset structure and by typeset structure its degree, then let

q _ 2(x)= lead(r _ 1(x)) b _ m^(-1) x^(n _ 1 - m),

r _ 2(x)= r _ 1(x) - q _ 2(x) q(x) .

Again, typeset structure. If typeset structure the procedure ends.  If typeset structure, then we proceed analogically as in the previous step to find polynomial typeset structure. Since the degrees of  polynomials typeset structure with growing index typeset structure decrease, after a finite number of steps we reach a value less than typeset structure. Let typeset structure denote the number of these steps, i.e.

q _ k(x)= lead(r _ (k - 1)(x)) b _ m^(-1) x^(n _ (k - 1) - m),

r _ k(x)= r _ (k - 1)(x) - q _ (k - 1)(x) q(x),

while typeset structure. Put

q(x) = q _ 1(x) + ... + q _ (k - 1)(x)            and       r(x) = r _ k(x) .

Then the backwards substitution yields that

a(x) = b(x) q(x) + r(x)

and the first conclusion of the Theorem about the existence follows.

Finally, in order to establish the uniqueness of typeset structure and typeset structure, let us suppose that typeset structure has two representations of the required form

a(x) = q(x) b(x) + r(x) = q^*(x) b(x) + r^*(x)

with typeset structure and typeset structure. Then

b(x) (q(x) - q^*(x)) = r^*(x) - r(x) .

Since typeset structure, this equality can hold only if  typeset structure, i.e. typeset structure and  typeset structure.

Example: The long division of polynomials demonstrated in the previous proof can be practically realized as follows:

4 3 ... 2

i.e. typeset structure.

The assumption that typeset structure is a field is essential, it is not possible to replace it, for instance, by a weaker assumption that typeset structure is a ring, because the division process by the leading coefficient of polynomial typeset structure could possibly not have been carried out in typeset structure if typeset structure is “only” a ring. Clearly,  the division can be realized if the leading coefficient of typeset structure has its multiplicative inverse in typeset structure,  for instance, when the leading coefficient is typeset structure or typeset structure.

Notes

1 typeset structure denotes the zero polynomial, i.e. typeset structure.

Cite this web-page as:

Štefan Porubský: Division of Polynomials.

Page created  .