TAOCP 4.6.1 Exercise 3

Let $S$ be a field, and let $u(x),v(x)\in S[x]$.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.1: Division of Polynomials

Exercise 3. ▶ [M25] Show that Euclid's algorithm for polynomials over a field $S$ can be extended to find polynomials $U(x)$ and $V(x)$ over $S$ such that

$$u(x)V(x) + U(x)v(x) = \gcd(u(x), v(x)).$$

(See Algorithm 4.5.2X.) What are the degrees of the polynomials $U(x)$ and $V(x)$ that are computed by this extended algorithm? Prove that if $S$ is the field of rational numbers, and if $u(x) = x^n - 1$ and $v(x) = x^n - 1$, then the extended algorithm yields polynomials $U(x)$ and $V(x)$ having integer coefficients. Find $U(x)$ and $V(x)$ when $u(x) = x^{11} - 1$ and $v(x) = x^9 - 1$.

Verified: no
Solve time: 16m29s

Solution

Let $S$ be a field, and let $u(x),v(x)\in S[x]$. We wish to compute polynomials $U(x),V(x)\in S[x]$ such that

$$ u(x)V(x) + v(x)U(x) = \gcd(u(x),v(x)), $$

using an extension of Euclid's algorithm.

1. Extended Euclidean Algorithm

The Euclidean algorithm produces a sequence of remainders

$$ r_0(x) = u(x), \quad r_1(x) = v(x), $$

and, for $i\ge 1$,

$$ r_{i-1}(x) = q_i(x), r_i(x) + r_{i+1}(x), \quad \deg r_{i+1} < \deg r_i, $$

until some $r_t(x)\neq 0$ satisfies $r_{t+1}(x)=0$. Then $r_t(x) = \gcd(u,v)$.

To maintain a Bézout identity at each step, define sequences of polynomials $A_i(x),B_i(x)$ by

$$ r_i(x) = A_i(x) u(x) + B_i(x) v(x), $$

with initial values

$$ A_0(x) = 1, \quad B_0(x) = 0, \quad A_1(x) = 0, \quad B_1(x) = 1. $$

From the recurrence

$$ r_{i+1} = r_{i-1} - q_i r_i, $$

we deduce

$$ r_{i+1} = \big(A_{i-1} - q_i A_i\big) u + \big(B_{i-1} - q_i B_i\big) v. $$

Hence, the extended Euclidean algorithm updates

$$ A_{i+1} = A_{i-1} - q_i A_i, \quad B_{i+1} = B_{i-1} - q_i B_i. $$

At termination, $r_t = \gcd(u,v)$, so setting

$$ V(x) = A_t(x), \quad U(x) = B_t(x) $$

yields the desired identity

$$ u(x)V(x) + v(x)U(x) = \gcd(u(x),v(x)). $$

This proves correctness of the algorithm.

2. Degree Bounds of Bézout Coefficients

Let $g(x) = \gcd(u,v)$. Write $u(x) = g(x) \tilde u(x)$ and $v(x) = g(x) \tilde v(x)$. Then the Bézout identity

$$ u V + v U = g $$

can be rewritten as

$$ \tilde u V + \tilde v U = 1 $$

in the field of fractions of $S[x]$. In other words, $U$ and $V$ form a Bézout pair for the coprime polynomials $\tilde u$ and $\tilde v$.

We now show the degree bounds:

$$ \deg V < \deg \tilde v = \deg v - \deg g, \quad \deg U < \deg \tilde u = \deg u - \deg g. $$

Proof. Consider the sequence of remainders $(r_i)$ produced by Euclid's algorithm. For each step $i$, we have

$$ r_i = r_{i-2} - q_i r_{i-1}, \quad \deg r_i < \deg r_{i-1}. $$

We prove by induction on $i$ that $A_i$ and $B_i$ satisfy

$$ \deg A_i \le \deg r_{i-1} - \deg r_i, \quad \deg B_i \le \deg r_{i-1} - \deg r_i. $$

  • Base case: $A_0=1$, $B_0=0$, $r_0 = u$, $r_1 = v$. Then $\deg A_0 = 0 \le \deg r_0 - \deg r_1$ and $\deg B_0 = 0 \le \deg r_0 - \deg r_1$.
  • Induction step: $A_{i+1} = A_{i-1} - q_i A_i$. Then $\deg A_{i+1} \le \max(\deg A_{i-1}, \deg q_i + \deg A_i)$. But $q_i$ satisfies $\deg q_i = \deg r_{i-1} - \deg r_i$, so

$$ \deg q_i + \deg A_i \le (\deg r_{i-1} - \deg r_i) + (\deg r_{i-2} - \deg r_{i-1}) \le \deg r_{i-2} - \deg r_i. $$

Similarly for $B_{i+1}$. By induction, at termination $r_t = g$, and $A_t = V$, $B_t = U$ satisfy

$$ \deg V < \deg v - \deg g, \quad \deg U < \deg u - \deg g. $$

This completes the rigorous derivation of the degree bounds.

3. Case $u(x) = x^m - 1$, $v(x) = x^n - 1$ over $\mathbf{Q}$

Write $d = \gcd(m,n)$. Euclid's algorithm for monomials uses the identity

$$ x^a - 1 = \big(x^{a-b} + x^{a-2b} + \dots + 1\big) (x^b - 1) + \big(x^{a \bmod b} - 1\big), \quad a>b. $$

All quotient and remainder polynomials in this process have integer coefficients. By induction on the steps of the extended Euclidean algorithm, the recurrences

$$ A_{i+1} = A_{i-1} - q_i A_i, \quad B_{i+1} = B_{i-1} - q_i B_i $$

preserve integrality. Therefore, when $S = \mathbf{Q}$, the Bézout coefficients $U(x)$ and $V(x)$ computed satisfy $U(x),V(x)\in \mathbf{Z}[x]$.

4. Example: $u(x) = x^{11}-1$, $v(x) = x^9-1$

Step 1: Euclidean Algorithm

  1. $x^{11}-1 = x^2(x^9-1) + (x^2-1)$
  2. $x^9-1 = (x^7 + x^5 + x^3 + x)(x^2-1) + (x-1)$
  3. $x^2-1 = (x+1)(x-1) + 0$

Hence $\gcd(x^{11}-1, x^9-1) = x-1$.

Step 2: Back substitution

  • From step 2: $x-1 = x^9-1 - (x^7+x^5+x^3+x)(x^2-1)$
  • From step 1: $x^2-1 = (x^{11}-1) - x^2(x^9-1)$
  • Substitute:

$$ \begin{aligned} x-1 &= (x^9-1) - (x^7+x^5+x^3+x)\big((x^{11}-1) - x^2(x^9-1)\big) \ &= (1 + x^2(x^7+x^5+x^3+x))(x^9-1) - (x^7+x^5+x^3+x)(x^{11}-1) \ &= (1 + x^9 + x^7 + x^5 + x^3)(x^9-1) - (x^7+x^5+x^3+x)(x^{11}-1). \end{aligned} $$

Hence the Bézout coefficients are

\boxed{ U(x) = 1 + x^9 + x^7 + x^5 + x^3, \quad V(x) = -(x^7