Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

Division of polynomials

by , PhD

The division of two polynomials is similar to the division of two integer numbers: as a result of the division, we get another polynomial and a remainder whose degree is less than that of the divisor.

Table of Contents

Polynomial

Remember that, given a field F (e.g., the set of real numbers R or the set of complex numbers $U{2102} $) and a non-negative integer $m$, a polynomial of degree $m$ is a function $f:F
ightarrow F$ defined by[eq1]where both the argument $z$ and the coefficients [eq2] belong to F and $a_{m}
eq 0$.

We denote the degree of a polynomial $f$ by [eq3].

Sum of polynomials

In this section and the next one we are going to revise some facts about sums and products of polynomials.

Recall that two polynomials are summed by summing their coefficients.

If $f$ is the polynomial of degree $m$ defined above and $g$ is another polynomial of degree $nleq m$ defined by[eq4]then[eq5]

The degree of $f+g$ is less than or equal to the degree $m$ of the higher-degree polynomial $f$. In particular, note that if $m=n$ and $a_{m}=-b_{m}$, then the degree of $f+g$ is less than $m$.

Example Let $f$ be the polynomial of degree $m=3$ defined by [eq6]and $g$ the polynomial of degree $2$ defined by[eq7]Then, the sum $f+g$ is the polynomial of degree $m=3$ defined by[eq8]

Product of polynomials

As before, let[eq9]The product $fg$ is[eq10]where the coefficients satisfy[eq11]

Since $a_{m}
eq 0$ and $b_{n}
eq 0$ (otherwise $f$ and $g$ would not be polynomials of degree $m$ and n respectively), $c_{n+m}
eq 0$ and $fg$ is a polynomial of degree $m+n$.

Example Let $f$ and $g$ be the polynomials defined in the previous example. Then,[eq12]and[eq13]

Division algorithm

The following proposition goes under the name of Division Algorithm because its proof is a constructive proof in which we propose an algorithm for actually performing the division of two polynomials.

Proposition Let $f$ and $g$ be two polynomials and [eq14]. Then, there exists a unique polynomial $q$ such that [eq15]and [eq16]. Moreover, $q=0$ when [eq17], or [eq18]when [eq19].

Proof

Let[eq20]and[eq21]where [eq22] and [eq23]. If $m<n$, then we obtain a representation of the desired form by setting $q=0$ and $r=f $. If $mgeq n$, then we define[eq24]where $b_{n}
eq 0$ because [eq25]. By multiplying the polynomial $gleft( z
ight) $ by [eq26], we transform it into a polynomial having the same degree $m$ as $fleft( z
ight) $ and the same leading coefficient $a_{m}$. Thus, [eq27] has at least one degree less than $fleft( z
ight) $. We now have[eq28]where[eq29]Since [eq30], if [eq31], we are done. Otherwise, we define[eq32]where $c$ is the leading coefficient of $r_{1}$ and [eq33]. We now have[eq34]where we have defined[eq35]Note that [eq36]Therefore, if [eq37], we are done. Otherwise, we keep lowering the degree of the remainder with the same technique used in the previous steps, until in step p we obtain[eq38]where [eq39] has degree $m-n$ and [eq40]. We now prove uniqueness by contradiction. Suppose that there are two representations having the desired characteristics:[eq41]where $q_{1}
eq q_{2}$. Then, we have[eq42]Since $q_{1}-q_{2}
eq 0$, the polynomial [eq43] has degree greater than or equal to [eq44]. The same must be true of $r_{1}$ or $r_{2}$. But this is impossible because the degrees of $r_{1}$ and $r_{2}$ must be less than [eq44]. Hence we have a contradiction, and it must be that $q_{1}=q_{2}$.

Terminology

We use the following terminology for the four polynomials involved in the division algorithm[eq46]

No remainder

If the remainder obtained at the end of the division algorithm is identically zero, that is, $r=0$ and[eq47]then we say that $g$ divides $f$, that $g$ is a divisor of $f$ or that $f$ is divisible by $g$, and we write[eq48]

Note that the requirement that [eq49] means that the zero polynomial can never be a divisor.

The zero polynomial as dividend

Note that if the dividend $f$ is identically equal to zero, then, for every $g$ with [eq49], we have[eq51]

Therefore, [eq52]for every $g.$

Example

Let us make an example to see how the division algorithm works in practice.

In order to understand the example, we need to first read the proof of the Division Algorithm (above), where the steps of the algorithm are explained.

Example Let us divide the polynomial[eq53]by the polynomial[eq54]Here [eq55] and [eq56]. We define [eq57]Thus,[eq58]and[eq59]The degree of $r_{1}$ is larger than that of $g$. As a consequence, we need to further reduce the degree of the remainder. The previous calculations are displayed synthetically as [eq60]where we have reported the dividend $fleft( z
ight) $ in the second row, the divisor $gleft( z
ight) $ in the leftmost column, the quotient [eq61] in the first row, the product [eq62] in the third row and the remainder [eq63] in the last row. The next steps of the algorithm are performed directly on the tableau:[eq64]In the last row, the degree of the remainder is less than that of the divisor, so we can stop the algorithm. The result of the division is[eq65]

Mutual divisors

Here is a simple but extremely useful fact about polynomials that are divisors of each other.

Proposition Let $f_{1}$ and $f_{2}$ be two polynomials not identically equal to zero. If $f_{1}|f_{2}$ and $f_{2}|f_{1}$, then [eq66]where $c$ is a non-negative constant belonging to F.

Proof

The fact that $f_{1}|f_{2}$ implies that there is no remainder in their division. By looking at the Division Algorithm, we can see that this happens only in the case in which [eq67] (it also happens when [eq68] and $f_{1}=0$, but $f_{1}
eq 0$ by assumption). Similarly, the fact that $f_{2}|f_{1}$ implies that [eq69]. Therefore, we have that[eq70]Let[eq71]where $c$ is the quotient of the division. By the properties of the multiplication of polynomials (reviewed above), we have[eq72]Therefore,[eq73]Thus, $c$ is a polynomial of degree zero, that is, a non-negative constant.

The remainder theorem

Here is an application of the Division Algorithm, called Remainder Theorem.

Proposition Let $f:F
ightarrow F$ be a polynomial and $ain F$. If we divide $fleft( z
ight) $ by $left( z-a
ight) $, we obtain $fleft( a
ight) $ as a remainder.

Proof

By applying the Division Algorithm, we obtain[eq74]where the degree of $r$ needs to be lower than the degree of $left( z-a
ight) $. The degree of the latter is 1. Therefore, $rleft( z
ight) $ is a constant. Thus, we have[eq75]or[eq76]

The factor theorem

Here is a corollary of the previous proposition, known as Factor Theorem.

Proposition Let $f:F
ightarrow F$ be a polynomial and $ain F$. Then, $fleft( z
ight) $ is divisible by $left( z-a
ight) $ if and only if a is a root of $f$.

Proof

By definition, $fleft( z
ight) $ is divisible by $left( z-a
ight) $ if and only if the remainder of the division is zero, which, by the Remainder theorem, happens if and and only if [eq77], which in turn happens if and only if a is a root of $f$.

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

Divide the polynomial[eq78]by the polynomial[eq79]

Solution

We need to perform only a single step: [eq80] The result of the division is[eq81]

How to cite

Please cite as:

Taboga, Marco (2017). "Division of polynomials", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/division-of-polynomials.

The book

Most of the learning materials found on this website are now available in a traditional textbook format.