Division with remainder for polynomials

Basic functions: Rational functions

Division with remainder for polynomials

Just as you can introduce division with remainder and long division with natural numbers not equal to zero, this is also possible for qoutients of polynomials. For example, you can write a rational function $\dfrac{P(x)}{Q(x)}$ with $P(x)$ a polynomial with degree greater than or equal to the degree of the polynomial $Q(x)$ in another form. The example below illustrates this.

$\begin{array}[t]{rrl} x^2+5\; \Bigm/ \!\!\! & 3x^3-x^2+16x-10 & \!\!\! \Bigm{\backslash} \; 3x-1 \\ & \underline{3x^3\phantom{abcd}\,\,+15x}\phantom{abef}\, & \qquad \blue{\uparrow}\\ & \phantom{0}-x^2\,+\phantom{15}x-10 & \blue{\text{quotient}}\\ & \phantom{0} \underline{-x^2\,\phantom{abcdefg}-5} & \\ & \phantom{0}x\,-\,5 & \blue{ \leftarrow \text{remainder}} \end{array}$ So: $3x^3-x^2+16x-10= (3x-1)\cdot (x^2+5) +x-5$ and $\frac{3x^3-x^2+16x-10}{x^2+5}=3x-1 \text{ mod }x-5\text.$

If the remainder is equal to zero, then we say that "the division terminates". Occasionally this can be seen immediately when you recognise a factor in the numerator, as in the example below.

$\begin{aligned}\frac{x^3+1}{x+1} &= \frac{(x+1)(x^2-x+1)}{x+1}\\[0.25cm] &= x^2-x+1\end{aligned}$ Note: this is a formal calculation, because strictly speaking the rational function on the left-hand side is not defined in $x=-1$ , but the rational function on the right-hand side is. The division thus yields the continuous continuation of the function on the left-hand side.

Long division is not necessary for a fractional linear function, as the example below illustrates.

$\begin{aligned}\frac{x+1}{x+2} &= \frac{(x+2)-1}{x+2}\\[0.25cm] &=1-\frac{1}{x+2}\end{aligned}$

Long division is a realisation of the following algorithm for the so-called Euclidean division for polynomials.

To divide a polynomial $p(x)$ , the 'dividend', with remainder by the divisor $d(x)$ , you can proceed as follows:

Put the terms in $p(x)$ and $d(x)$ in descending order of degree. Missing powers in the dividend can be supplemented with coefficients zero or just leave it blank..
Divide the leading term of $p(x)$ by the leading term of $d(x)$ . This gives you a provisional quotient.
Multiply this first term of the quotient by the divisor and subtract this product from the dividend $p(x)$ . This gives a provisional remainder.
Divide the leading term of the provisional remainder by the leading term of the divisor, and add the result as a new term to the provisional quotient. This gives a new provisional quotient.
Multiply the new component by the divisor and subtract this product from the dividend. This gives you a new provisional remainder.
Repeat the previous two steps until the degree of the provisional remainder is strictly less than the degree of the divisor.
The last provisional remainder is then the remainder sought.

$\begin{array}[t]{rrl} x^2-1\; \Bigm/ \!\!\! & x^4+2x^3+3x^2+4x+5 & \!\!\! \Bigm{\backslash} \; x^2+2x+4 \\ & \underline{x^4\phantom{+2x^3}\;\;-x^2\phantom{+4x+5}\;\;\;} & \qquad\qquad\qquad \blue{\leftarrow x^2\text{ in }x^4\text{ goes }x^2\text{ times}}\\ & 2x^3+4x^2+4x+5 & \qquad\qquad\qquad \blue{\leftarrow\text{subtract}}\\ & \underline{2x^3\phantom{+4x^2}\;-2x\phantom{+5}\;\;} & \qquad\qquad\qquad \blue{\leftarrow x^2\text{ in }2x^3\text{ goes }2x\text{ times}}\\ & 4x^2+6x+5 & \qquad\qquad\qquad\blue{\leftarrow\text{substract}}\\ & \underline{4x^2\phantom{+6x}\;\,-4} & \qquad\qquad\qquad \blue{\leftarrow x^2\text{ in }4x^2\text{ goes }4\text{ times}}\\ & 6x+9 & \qquad\qquad\qquad\blue{\leftarrow\text{subtract}}\\ \end{array}$ So: $x^4+2x^3+3x^2+4x+5= (x^2+2x+4)\cdot (x^2-1) +6x-9$ and $\frac{x^4+2x^3+3x^2+4x+5}{x^2-1}=x^2+2x+4 \textit{ mod }6x+9\text.$

Wehn you follow the algortithm as it is written above, then an elaboration can look like the below randomised example.

Consider $\begin{aligned}p(x)&=-x^4-2\,x^3-x+3\\[0.25cm] d(x)&=-x^2-1\end{aligned}$ Divide $p(x)$ by $d(x)$ with remainder, that is, determine the quotient $q(x)$ and the remainder $r(x)$ such that $p(x)=q(x)\cdot d(x)+r(x)$ .

$q(x)={}$ $x^2+2\, x-1$

$r(x)={}$ $x+2$

So: $-x^4-2\,x^3-x+3 = (x^2+2\, x-1)(-x^2-1)+x+2$

$\begin{array}{ll} \text{Step 1:}&\text{The terms of the dividend } p=-x^4-2x^3-x+3\\ &\text{and in the divisor }d=-x^2-1 \text{ are in descending order of degree.}\\ &\text{Set the provisional remainder to }0\text{.}\\\text{Step 2:} &\text{Divide the leading term of }-x^4-2x^3-x+3\\ & \text{by the leading term of }-x^2-1\text{.}\\ & \text{In this case, division of }-x^4\text{ by }-x^2\text{ leads to the new term }x^2\\ & \text{of the provisional quotient.} \\\text{Step 3:} &\text{Multiply the newly computed term of the provisional quotient}\\ &\text{by the divisor and subtract this product from the dividend. This gives you a new provisional remainder.}\\ &\text{It is in this case equal to }-2x^3+x^2-x+3\text{.}\\\text{Step 4:} &\text{Divide the leading term of }-2x^3+x^2-x+3\\ & \text{by the leading term of }-x^2-1\text{.}\\ & \text{In this case, division of }-2x^3\text{ by }-x^2\text{ leads to the new term }2x\\ & \text{of the provisional quotient.} \\\text{Step 5:} &\text{Multiply the newly computed term of the provisional quotient}\\ &\text{by the divisor and subtract this product from the dividend. This gives you a new provisional remainder.}\\ &\text{It is in this case equal to }x^2+x+3\text{.}\\\text{Step 6:} &\text{Divide the leading term of }x^2+x+3\\ & \text{by the leading term of }-x^2-1\text{.}\\ & \text{In this case, division of }x^2\text{ by }-x^2\text{ yieds the new term }-1\\ & \text{of the provisional quotient.} \\\text{Step 7:} &\text{Multiply the newly computed term of the provisional quotient}\\ &\text{by the divisor and subtract this product from the dividend. This gives you a new provisional remainder.}\\ &\text{It is in this case equal to }x+2\\\text{Step 8:} & \text{The degree of the provisional remainder is now less than the degree of the divisor; the algorithm ends.} \\ & \text{The remainder of the division is equal to the last computed provisional remainder.} \\ & \text{remainder}=x+2\\ & \text{Addition of the terms of the provisional quotient found in earlier step gives:} \\ & \text{quotient}=x^2+2x-1\end{array}$

New example

Another, but less efficient method for long division follows a direct approach that makes use of systems of lineare equations; see the below randomised example.

Suppose $p(x)=-2\, x^6+2\, x^5-3\, x^4+2\, x^3+3\, x^2-2\, x+7$ and $d(x)=x^3-x^2+x-2$ Divide $p(x)$ by $d(x)$ with remainder, that is, determine the quotient $q(x)$ and the remainder $r(x)$ such that $p(x)=q(x)\cdot d(x)+r(x)$ .

$q(x)={}$ $-2\, x^3-x-3$

$r(x)={}$ $x^2-x+1$

Note first that the degree of the requested quotient is $3$ , which is the difference between the degree of $p(x)$ and the degree of $d(x)$ . Set $q(x)=a\, x^3+b\, x^2+c\, x+d$ .

Because $p(x)=q(x)\cdot d(x)+r(x)$ and the degree of $r(x)$ is less than the degree of $d(x)$ , i.e., less than $2$ , the terms of degree greater than $2$ must be equal to those of $q(x)\cdot d(x)$ . Equating the coefficients of $x^7, x^6\ldots,x^3$ in $p(x)$ with those of the product $q(x)\cdot d(x)$ gives the following system of linear equations in the unknowns $a$ , $b$ , $c$ , $d$ , $e$ .
$\left[ -2=a , 2=b-a , -3=c-b+a , 2=d-c+b-2\, a \right]$ The solution of this system is $\left[ a=-2 , b=0 , c=-1 , d=-3 \right]$ Substitution in $q(x)=a\, x^3+b\, x^2+c\, x+d$ yields quotient: $q(x)=-2\, x^3-x-3$ The remainder of division can be calculated using $r(x)=p(x)-q(x)\cdot d(x)$ and eliminating the parentheses. The result is $r(x)=x^2-x+1$

New example