TAOCP 4.6.1 Exercise 14

Let u(x)=u_mx^m+\cdots,\qquad v(x)=ax^n+\cdots, where $a=l(v)$, and let $m=\deg(u)$, $n=\deg(v)$.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.1: Division of Polynomials

Exercise 14. [M23] Let $r(x)$ be the pseudo-remainder when $u(x)$ is pseudo-divided by $v(x)$. If $\deg(u) \ge \deg(v) + 2$ and $\deg(u) \ge \deg(v) + 2$, show that $r(x)$ is a multiple of $l(v)$.

Verified: yes
Solve time: 4m16s

Solution

Let

$$ u(x)=u_mx^m+\cdots,\qquad v(x)=ax^n+\cdots, $$

where $a=l(v)$, and let $m=\deg(u)$, $n=\deg(v)$. Assume that

$$ m\ge n+2. $$

Recall the pseudo-division algorithm. Starting with $U_0=u$, one constructs polynomials $U_1,U_2,\ldots,U_{m-n+1}$ by

$$ U_{i+1}=aU_i-c_i x^{d_i}v, $$

where $c_i=l(U_i)$ and $d_i=\deg(U_i)-n$. The leading term of $U_i$ is thereby canceled, so that

$$ \deg(U_{i+1})<\deg(U_i). $$

The pseudo-remainder is

$$ r=U_{m-n+1}. $$

We prove that $a\mid r$.

Since $m\ge n+2$, the algorithm performs at least two pseudo-division steps. Consider the first step:

$$ U_1=aU_0-c_0x^{m-n}v. $$

Write $c_0=u_m$. Because $v=ax^n+\cdots$,

$$ c_0x^{m-n}v =c_0ax^m+\text{(lower-degree terms)}. $$

Hence the coefficient of $x^m$ cancels against the leading term of $aU_0$, and every remaining coefficient of $U_1$ is a difference of two terms, each containing the factor $a$. Therefore

$$ U_1=aW_1 $$

for some polynomial $W_1\in S[x]$.

Now perform the second step:

$$ U_2=aU_1-c_1x^{d_1}v. $$

Since $U_1=aW_1$, every coefficient of $U_1$ is divisible by $a$. In particular its leading coefficient $c_1=l(U_1)$ satisfies

$$ a\mid c_1. $$

Write $c_1=ab_1$. Then

$$ U_2 =a(aW_1)-ab_1x^{d_1}v =a\bigl(aW_1-b_1x^{d_1}v\bigr). $$

Thus $a\mid U_2$.

We now show by induction that

$$ a\mid U_i\qquad(i\ge2). $$

Assume $a\mid U_i$. Then $a\mid l(U_i)=c_i$, so $c_i=ab_i$ for some $b_i\in S$. The next pseudo-division step gives

$$ U_{i+1} =aU_i-c_ix^{d_i}v =aU_i-ab_ix^{d_i}v =a\bigl(U_i-b_ix^{d_i}v\bigr), $$

hence $a\mid U_{i+1}$.

Therefore every $U_i$ with $i\ge2$ is divisible by $a$.

Since $m\ge n+2$, the pseudo-remainder is obtained after $m-n+1\ge3$ polynomials in the sequence, namely

$$ r=U_{m-n+1}, $$

and $m-n+1\ge2$. Consequently $r$ belongs to the range covered by the induction, so

$$ a\mid r. $$

Because $a=l(v)$, it follows that the pseudo-remainder $r(x)$ is a multiple of $l(v)$.

$$ \boxed{,l(v)\mid r(x), }. $$

∎