TAOCP 4.6.1 Exercise 6

**Exercise 4.

taocpmathematicsalgorithmsvolume-2math-hard

Section 4.6.1: Division of Polynomials

Exercise 6. [M29] We showed that Euclid's Algorithm 4.5.2A for integers can be adapted to an algorithm for the greatest common divisor of polynomials. Can the binary gcd algorithm, Algorithm 4.5.2B, be adapted in an analogous way to an algorithm that applies to polynomials?

Verified: no
Solve time: 10m41s

Exercise 4.6.1.6 [M29]

We showed that Euclid's Algorithm 4.5.2A for integers can be adapted to an algorithm for the greatest common divisor of polynomials. Can the binary gcd algorithm, Algorithm 4.5.2B, be adapted in an analogous way to an algorithm that applies to polynomials?

Solution.

Yes.

To see why, examine the properties on which Algorithm 4.5.2B is based. For integers, the algorithm uses:

  1. A distinguished prime factor, namely $2$.
  2. The fact that common powers of $2$ can be removed:

$$ \gcd(2^e m,2^e n)=2^e\gcd(m,n). $$ 3. The identity

$$ \gcd(m,n)=\gcd(m-n,n), $$

which allows reduction by subtraction. 4. The fact that after removing powers of $2$, every integer is either odd or even.

For polynomials over a field $F$, choose any fixed irreducible polynomial $p(x)$. Let

$$ \nu_p(f) $$

denote the exponent of $p(x)$ in $f(x)$. Then the exact analogue of the integer property holds:

$$ \gcd!\bigl(p(x)^e u(x),, p(x)^e v(x)\bigr) = p(x)^e \gcd(u(x),v(x)). $$

Hence common powers of $p(x)$ may be extracted exactly as common powers of $2$ are extracted in the integer algorithm.

Now write

$$ f(x)=p(x)^a f_1(x),\qquad g(x)=p(x)^b g_1(x), $$

where $p\nmid f_1$ and $p\nmid g_1$. Then

$$ \gcd(f,g) = p(x)^{\min(a,b)}\gcd(f_1,g_1). $$

After removing the common power $p(x)^{\min(a,b)}$, both $f_1$ and $g_1$ are not divisible by $p(x)$.

The subtraction property also remains valid:

$$ \gcd(f,g)=\gcd(f-g,g). $$

However, to obtain degree reduction analogous to the integer case, one first cancels the leading term of the polynomial of larger degree. If

$$ \deg f \ge \deg g, $$

let

$$ c=\frac{\operatorname{lc}(f)}{\operatorname{lc}(g)} $$

and replace $f$ by

$$ f-cx^{\deg f-\deg g}g. $$

This operation preserves the gcd and strictly decreases the degree of $f$. It is precisely the subtraction-type step underlying polynomial division.

Thus the ingredients of the binary gcd algorithm have polynomial analogues:

  • powers of $2$ correspond to powers of a fixed irreducible polynomial $p(x)$;
  • removal of common powers is handled by the valuation $\nu_p$;
  • subtraction is replaced by subtraction after suitable monomial scaling so that leading terms cancel.

Consequently a binary-style gcd algorithm for polynomials can indeed be formulated. It is not especially advantageous, because polynomial division already achieves degree reduction efficiently, and the resulting procedure is essentially another form of the Euclidean algorithm. Nevertheless, there is no mathematical obstruction analogous to the one suggested by the flawed argument.

Therefore the answer is yes: the binary gcd method can be adapted to polynomials by replacing divisibility by $2$ with divisibility by a fixed irreducible polynomial and using degree-reducing subtraction steps.