Division with remainder for polynomials

Matrix calculus: Minimal polynomial

Division with remainder for polynomials

We need division with remainder for polynomials in order to discuss the notion of minimal polynomial for matrices and linear maps.

Division with remainder for polynomials is slightly more complicated than addition, subtraction and multiplication, especially since not every division yields a polynomial. This process is comparable to division with remainder for integers. The integer case involves a comparison of integers by their size (absolute value). For polynomials, the degree is the appropriate measure.

We recall that the degree of a polynomial in $x$ is the highest exponent of $x$ occurring in the expanded form (as a sum of products of a coefficient with a power of $x$ having a non-negative exponent) of that polynomial. We denote the degree of the polynomial $f(x)$ by $\text{deg}(f(x))$ .

If $f(x)= 0$ , the zero polynomial, it is practical to define the degree of $f(x)$ to be $-1$ . If $f$ is a nonzero polynomial of degree $n$ , the coefficient of $x^n$ in the expanded form of $f(x)$ is called the leading coefficient of $f(x)$ . A polynomial is said to be monic if its leading coefficient is equal to $1$ .

A polynomial of degree $1$ is called linear. A polynomial of degree $2$ is called quadratic.

Examples

The expanded form $(x+3)^4-x^2-1$ is equal to $x^4+12x^3+53x^2+108x+80$ . The degree of this monic polynomial is $4$ .
The degree of $(x+3)^4-x^4-1$ is $3$ , for its expanded form is $12x^3+54x^2+108x+80$ . Its leading coefficient is $12$ , so it is not monic.

Division with remainder starts with the definition of divisors:

A polynomial $g(x)$ is called a divisor of a polynomial $f(x)$ if there is a polynomial $q(x)$ such that $f(x) = q(x)\cdot g(x)$ . In that case, $g(x)$ divides $f(x)$ . If $g(x)\ne0$ , the polynomial $q(x)$ is unique. It is called the quotient of $f(x)$ and $g(x)$ .

If the degree of $g(x)$ is smaller than the degree of $f(x)$ , then $g(x)$ is called a proper divisor.

We show that the quotient is unique. Suppose that $g(x)\ne0$ , and that $q_1(x)$ and $q_2(x)$ are polynomials satisfying $q_1(x)g(x) = q_2(x)g(x)$ . Then $(q_1(x) - q_2(x))\cdot g(x)=0$ , so $q_1(x) - q_2(x) = 0$ , proving $q_1(x) = q_2(x)$ .

Because $1$ is a polynomial satisfying $f(x)=1\cdot f(x)$ , the polynomial $f(x)$ is a divisor of $f(x)$ .

Also, each constant multiple of $f(x)$ distinct from $0$ is a divisor of $f(x)$ : if $a$ is a real number, which is not equal to $0$ , then $q(x) = \frac{1}{a}$ is a polynomial for which $f(x)=q(x)\cdot\left(a\cdot f(x)\right)$ holds, so $a\cdot f(x)$ is a divisor of $f(x)$ .

These are not proper divisors, though.

The polynomial $x^2-1$ is a divisor of $x^6-1$ , since $x^6-1=(x^2-1)\cdot (x^4+x^2+1)$ .

QuotientThe quotient is a special case of the quotient from division with remainder discussed below.

In order to find divisors, we use the equivalent of long division for the integers.

Let $f(x)$ be a polynomial of degree $m\ge1$ and $g(x)$ a polynomial of degree $n\ge0$ . We can test as follows whether $g(x)$ is a divisor of $f(x)$ . Denote by $b$ the leading coefficient of $g(x)$ .

There exist unique polynomials $q(x)$ and $r(x)$ such that $f(x) = q(x)\cdot g(x) + r(x)$ and the degree of $r(x)$ is smaller than $n$ .

The polynomial $q(x)$ can be found by starting with $q(x) =0$ and $r(x) = f(x)$ , and subsequently

as long as the degree $k$ of $r(x)$ is at least $n$ , subtracting from $r(x)$ the multiple $\dfrac{a}{b}x^{k-n}\cdot g(x)$ of $g(x)$ , where $a$ is the leading coefficient of $r(x)$ , and adding $\dfrac{a}{b}x^{k-n}$ to $q(x)$ .

Once the degree of $r(x)$ is smaller than $n$ , the polynomials $q(x)$ and $r(x)$ are found.

The polynomial $g(x)$ is a divisor of $f(x)$ if and only if $r(x) = 0$ .

The procedure for finding the quotient $q(x)$ and remainder $r(x)$ is chosen so that, at the end of each step in which $q(x)$ and $r(x)$ are changed, we have $f(x) = q(x) \cdot g(x) + r(x)$ . At each step, the degree of $r(x)$ goes down. Since the degree of $r(x)$ at the beginning is equal to the degree of $f(x)$ and at each step becomes at least $1$ less, the number of steps of the procedure will never exceed $m$ .

Suppose that $q_1(x)$ and $r_1(x)$ are two polynomials with $f(x) = q_1(x)\cdot g(x) + r_1(x)$ such that the degree of $r_1(x)$ is smaller than that of $g(x)$ . Then we have $q(x)\cdot g(x)+r(x) = f(x) = q_1(x)\cdot g(x) + r_1(x)$ which shows that $(q(x)-q_1(x))\cdot g(x) = r_1(x) - r(x)$ . The right-hand member is a polynomial of degree less than the degree of $g(x)$ , so the left-hand member is a polynomial of degree less than the degree of $g(x)$ . Being a multiple of $g(x)$ , it must be $0$ , so $q(x)-q_1(x)= 0$ . This means that $q_1(x) = q(x)$ . It follows that $0= (q(x)-q_1(x))\cdot g(x) = r_1(x) - r(x)$ so $r_1(x) = r(x)$ . This shows that the quotient $q(x)$ and the remainder $r(x)$ are indeed unique.

If $r(x) = 0$ , then $f(x) = q(x)\cdot g(x)$ , so $g(x)$ divides $f(x)$ .

Conversely, if $g(x)$ divides $f(x)$ , then there is a polynomial $s(x)$ with $f(x) = s(x)\cdot g(x) + 0$ . Because the degree of $0$ is smaller than the degree of $g(x)$ , the uniqueness forces $s(x) =q(x)$ and $r(x) = 0$ .

Example

The quotient $q(x)$ and remainder $r(x)$ of division of $f(x) = x^4+2x^3+3x^2+2x+1\quad{}\text{ by }\quad{} g(x) = x^2-1$ can be found by long division: $\begin{array}{lclcr} \color{blue}{x^2-1}&/&x^4+2x^3+3x^2+2x+1&\backslash&\color{green}{x^2}+\color{green}{2x}+\color{green}{4}\\ &&\underline{x^4\phantom{+00x^3}-\phantom{0}x^2\phantom{+0x+00}}&\leftarrow&\color{green}{x^2}\cdot\color{blue}{(x^2-1)}\\ &&\phantom{0x^4+}2x^3+4x^2+2x+1&&\\ &&\underline{\phantom{0x^4+}2x^3\phantom{+00x^2}-2x\phantom{+00}}&\leftarrow&\color{green}{2x}\cdot\color{blue}{(x^2-1)}\\&&\phantom{x^4+00x^3+}4x^2+4x+1&&\\ &&\underline{\phantom{x^4+00x^3+}4x^2\phantom{+00x}-4}&\leftarrow&\color{green}{4}\cdot\color{blue}{(x^2-1)}\\ &&\phantom{x^4+00x^3+4x^2+}\color{red}{4x+5}&&\end{array}$

So $f(x) = g(x)\cdot (x^2+2x+4)+4x+5$ . We conclude that $q(x) = x^2+2x+4$ and $r(x) = 4x+5$ .

Special case If the degree $n$ of $g(x)$ is bigger than the degree $m$ of $f(x)$ , then the quotient $q(x)$ and remainder $r(x)$ of division with remainder of $f(x)$ by $g(x)$ are given by $q(x)=0$ and $r(x)=f(x)$ . After all, already in the first step $\rv{q(x),r(x)}=\rv{0,f(x)}$ of the described algorithm, the degree of $r(x)$ is smaller than that of $g(x)$ .

Quotient function

Let us compare division with remainder for polynomials to division with remainder for integers.

For each pair of integers $n$ and $m\neq0$ there exist unique integers $q$ and $r$ such that $n=q\cdot m+r$ and $|r|\lt|m|$ . The quotient $n/m$ is generally a rational number that, if and only if $r=0$ , again equals an integer, namely $q$ . This can only happen if either $n=0$ (in which case also $q=0$ for all $m\neq0$ ) or $|n|\ge|m|$ . In the latter case $q\neq0$ holds and the absolute value of $q$ indicates how many times bigger $|n|$ is relative to $|m|$ , since $|n|=|q|\cdot|m|$ for $r=0$ .

For each pair of polynomials $f(x)$ and $g(x)\neq0$ there exist unique polynomials $q(x)$ and $r(x)$ such that $f(x)=q(x)\cdot g(x)+r(x)$ and $\text{deg}\left(r(x)\right)\lt\text{deg}\left(g(x)\right)$ . The quotient function $(f/g)(x)=f(x)/g(x)$ is generally a rational function that, if and only if $r(x)=0$ , again equals a polynomial, namely $q(x)$ , except at the zeros of $g(x)$ where $(f/g)(x)$ is not defined but $q(x)$ is (since a polynomial is defined everywhere). The remainder $r(x)$ can only become zero if either $\text{deg}\left(f(x)\right)=-1$ (meaning $f(x)=0$ , in which case also $q(x)=0$ holds for all $g(x)\neq0$ ) or $\text{deg}\left(f(x)\right)\ge\text{deg}\left(g(x)\right)$ . In the latter case $q(x)\neq0$ holds and the degree of $q(x)$ indicates the difference between the degree of $f(x)$ and that of $g(x)$ , since then $\text{deg}\left(q(x)\right)=\text{deg}\left(f(x)\right)-\text{deg}\left(g(x)\right)$

For example: for $f(x)=x^2-3x+2$ and $g(x)=x+1$ we find $q(x)=x-4$ and $r(x)=6$ . Because the remainder is unequal to zero, the quotient function $(f/g)(x)$ is not a polynomial. But for $f(x)=x^2-3x+2$ and $g(x)=x-1$ we find $q(x)=x-2$ and $r(x)=0$ , so that $(f/g)(x)$ equals the polynomial $q(x)$ everywhere except at $x=1$ where $q(x)$ equals $-1$ but $(f/g)(x)$ is undefined because $g(1)=0$ .

Determine the quotient $q(x)$ and the remainder $r(x)$ when dividing with remainder $f(x) = 2 x^3-4 x^2+7 x-4$ by $g(x) = x^2-x+2$ .

Do this by entering pairs $\rv{q(x),r(x)}$ such that $f(x) = q(x)\cdot g(x) + r(x)$ and the degree of $r(x)$ keeps getting smaller.

$\rv{q(x),r(x)} =$ $\rv{2 x-2,x}$

To see this, we follow the theory and start with $q(x) =0$ and $r(x) = f(x) = 2 x^3-4 x^2+7 x-4$ . The degree of $r(x)$ is bigger than $2$ , the degree of $g(x)=x^2-x+2$ . Therefore, we subtract $2 x \cdot g(x)$ from $r(x)$ and add $2 x$ to $q(x)$ . This gives $\rv{q(x),r(x)} = \rv{2 x,-2 x^2+3 x-4}$ The degree of $r(x)$ is not yet smaller than $2$ , so we repeat this process: we subtract $-2\cdot g(x)$ from $r(x)$ and add $-2$ to $q(x)$ . This gives $\rv{q(x),r(x)} = \rv{2 x-2,x}$ Now the degree of $r(x)$ is smaller than $2$ . The conclusion is that we have found the required $q(x)$ and $r(x)$ .

Since $r(x)\ne0$ , the polynomial $g(x)$ is not a divisor of $f(x)$ .

New example