TAOCP 4.6.1 Exercise 25
Let u_1(x),u_2(x),u_3(x),\ldots be the subresultant polynomial remainder sequence defined by equation (16) of Algorithm C.
Section 4.6.1: Division of Polynomials
Exercise 25. [M47] (W. S. Brown.) Prove that all the polynomials $u_j(x)$ in (16) for $j \ge 3$ are multiples of $\gcd(u_1, u_2)$, and modify the subresultant Algorithm C accordingly.
Verified: yes
Solve time: 4m57s
Let
$$ u_1(x),u_2(x),u_3(x),\ldots $$
be the subresultant polynomial remainder sequence defined by equation (16) of Algorithm C. Thus, for $j\ge2$,
$$ \beta_j u_{j+1} = \operatorname{prem}(u_{j-1},u_j), $$
where $\operatorname{prem}$ denotes pseudo-remainder, and $\beta_j$ is a nonzero element of the coefficient domain.
Let
$$ g(x)=\gcd(u_1,u_2), $$
chosen primitive. Write
$$ u_1=g a_1,\qquad u_2=g a_2, $$
where
$$ \gcd(a_1,a_2)=1. $$
We prove first that
$$ g\mid u_j\qquad (j\ge3). $$
Suppose inductively that
$$ g\mid u_{j-1},\qquad g\mid u_j. $$
Then there exist polynomials $v_{j-1},v_j$ such that
$$ u_{j-1}=gv_{j-1},\qquad u_j=gv_j. $$
Now every step of pseudo-division consists of replacing a polynomial $F$ by
$$ cF-q,u_j, $$
where $c$ is a scalar from the coefficient domain and $q\in R[x]$. Since both $F$ and $u_j$ are divisible by $g$, every such combination is divisible by $g$. Hence the final pseudo-remainder is divisible by $g$:
$$ g\mid \operatorname{prem}(u_{j-1},u_j). $$
Using the defining recurrence,
$$ \beta_j u_{j+1} = \operatorname{prem}(u_{j-1},u_j), $$
we obtain
$$ g\mid \beta_j u_{j+1}. $$
Since $g$ is primitive and $\beta_j$ is a nonzero scalar, $g$ and $\beta_j$ are relatively prime in $R[x]$. Therefore a primitive polynomial divisor of $\beta_j u_{j+1}$ must divide $u_{j+1}$. Hence
$$ g\mid u_{j+1}. $$
The induction begins with $u_1$ and $u_2$, so
$$ g\mid u_j\qquad (j\ge1). $$
In particular,
$$ g\mid u_j\qquad (j\ge3). $$
This proves the first assertion.
To modify Algorithm C, define
$$ u_j=g a_j\qquad (j\ge1). $$
Since $u_1=ga_1$ and $u_2=ga_2$, the sequence $(a_j)$ is primitive with
$$ \gcd(a_1,a_2)=1. $$
We now determine the recurrence satisfied by the $a_j$. Let
$$ m=\deg u_{j-1},\qquad n=\deg u_j, \qquad \delta_j=m-n. $$
Pseudo-division gives
$$ \operatorname{prem}(u_{j-1},u_j) = \operatorname{prem}(gv_{j-1},gv_j). $$
The pseudo-remainder is homogeneous in the following sense:
$$ \operatorname{prem}(gf,gh) = g^{\delta+1}\operatorname{prem}(f,h), $$
where
$$ \delta=\deg f-\deg h. $$
Indeed, pseudo-division of $f$ by $h$ multiplies the dividend by
$$ (\operatorname{lc} h)^{\delta+1}. $$
Replacing $h$ by $gh$ multiplies the leading coefficient by $\operatorname{lc}(g)$, while every subtraction term acquires a factor $g$. Consequently every term in the pseudo-remainder acquires the common factor $g^{\delta+1}$.
Applying this identity with $f=a_{j-1}$, $h=a_j$, and $\delta=\delta_j$, we obtain
$$ \operatorname{prem}(u_{j-1},u_j) = g^{\delta_j+1}\operatorname{prem}(a_{j-1},a_j). $$
Substituting into the recurrence,
$$ \beta_j g a_{j+1} = g^{\delta_j+1}\operatorname{prem}(a_{j-1},a_j), $$
hence
$$ \beta_j a_{j+1} = g^{\delta_j}\operatorname{prem}(a_{j-1},a_j). $$
Therefore the reduced sequence $(a_j)$ does not satisfy the same recurrence as $(u_j)$. An extra factor $g^{\delta_j}$ appears.
The correct modification of Algorithm C is therefore as follows.
Instead of carrying along the unreduced sequence $u_j$, compute at each stage the primitive part
$$ a_j=\operatorname{pp}(u_j). $$
Equivalently, after forming $u_{j+1}$, divide by the gcd of its coefficients and by any common polynomial factor inherited from preceding terms.
Since every $u_j$ contains the fixed factor $g$, this modification removes that persistent factor immediately. The algorithm then operates on primitive polynomials only, which reduces coefficient growth throughout the computation.
At termination, the gcd is recovered from the final nonzero primitive remainder. More precisely, if the reduced sequence terminates with
$$ a_t\ne0,\qquad a_{t+1}=0, $$
then
$$ \gcd(u_1,u_2) = g,a_t, $$
up to multiplication by a unit.
Thus the common polynomial factor may be systematically removed during the subresultant computation by replacing each remainder with its primitive part. This is the required modification of Algorithm C.
$\square$