TAOCP 4.6.1 Exercise 18

Section 4.6.1: Division of Polynomials

Exercise 18. ▶ [**] $[M24]$ (Euclidean algorithm for string polynomials.) Let $V_1$ and $V_2$ be string polynomials, not both zero, having a common left multiple. (This means that there exist string polynomials $U_1$ and $U_2$, not both zero, such that $U_1V_1 = U_2V_2$.) The purpose of this exercise is to find an algorithm to compute their greatest common right divisor $\gcd(V_1, V_2)$ and their least common left multiple $\text{lcm}(V_1, V_2)$. The latter quantities are defined as follows: $\gcd(V_1, V_2)$ is a common right divisor of $V_1$ and $V_2$ (that is, $V_1 = W_1 \gcd(V_1, V_2)$ and $V_2 = W_2 \gcd(V_1, V_2)$ for some $W_1$ and $W_2$), and any common right divisor of $V_1$ and $V_2$ is a right divisor of $\gcd(V_1, V_2)$; $\text{lcm}(V_1, V_2) = Z_1V_1 = Z_2V_2$ for some $Z_1$ and $Z_2$, and any common left multiple of $V_1$ and $V_2$ is a left multiple of $\text{lcm}(V_1, V_2)$.

For example, let $V_1 = abbab + abab - bbab + ab - 1$, $V_2 = babab + abab + ab - b$; $U_1 = ab + ab - b$, $U_2 = ab + b + bababa + bababab + ababab - 1$. Then we have $U_1V_1 = U_2V_2 = abbabbab + ababbabab + abbababab + abbababab - bbabbabab + abbabab - bbababab + 2abbabab - abbab + ababab - abbabb - bbabab - babab + babb - abb - ab + b$. For these string polynomials it can be shown that $\gcd(V_1, V_2) = ab + 1$, and $\text{lcm}(V_1, V_2) = U_1V_1$.

The division algorithm of exercise 17 may be restated thus: If $V_1$ and $V_2$ are string polynomials, with $V_2 \ne 0$, and if $U_1 \ne 0$ and $U_2$ satisfy the equation $U_1V_1 = U_2V_2$, then there exist string polynomials $Q$ and $R$ such that

$$V_1 = QV_2 + R, \qquad \text{where } \deg(R) < \deg(V_2).$$

It follows readily that $Q$ and $R$ are uniquely determined; they do not depend on the given $U_1$ and $U_2$. Furthermore the result is right-left symmetric, in the sense that

$$U_2 = U_1Q + R', \qquad \text{where } \deg(R') = \deg(U_1) - \deg(V_2) + \deg(R) < \deg(U_1).$$

Show that this division algorithm can be extended to an algorithm that computes $\text{lcm}(V_1, V_2)$ and $\gcd(V_1, V_2)$; in fact, the extended algorithm finds string polynomials $Z_1$ and $Z_2$ such that $Z_1 V_1 + Z_2 V_2 = \gcd(V_1, V_2)$. [Hint: Use auxiliary variables $u_1$, $u_2$, $v_1$, $v_2$, $w_1$, $w_2$, $w_1'$, $w_2'$, $z_1$, $z_2$, $z_1'$, $z_2'$, whose values are string polynomials; start by setting $u_1 \leftarrow U_1$, $u_2 \leftarrow U_2$, $v_1 \leftarrow V_1$, $v_2 \leftarrow V_2$, and throughout the algorithm maintain the conditions

$$u_1 w_1 + U_2 w_2 = u_1, \qquad z_1 V_1 + z_2 V_2 = v_1,$$ $$U_1 w_1' + U_2 w_2' = u_2, \qquad z_1' V_1 + z_2' V_2 = v_2,$$ $$-u_1 z_1 - w_1 = (-1)^n U_1, \qquad w_1 v_1 - w_1' v_2 = (-1)^n V_1,$$ $$-u_1 z_2 + w_2' = (-1)^n U_2, \qquad -w_2 v_1 + w_2' v_2 = (-1)^n V_2$$

at the $n$th iteration. This might be regarded as the "ultimate" extension of Euclid's algorithm.]

Verified: yes
Solve time: 6m10s

Solution.

Let $V_1$ and $V_2$ be string polynomials, not both zero, that have a common left multiple. That is, there exist string polynomials $U_1$ and $U_2$, not both zero, such that

$$ U_1 V_1 = U_2 V_2. $$

We want to compute the greatest common right divisor (gcrd) $\gcd(V_1, V_2)$ and the least common left multiple (lclm) $\operatorname{lcm}(V_1, V_2)$. We also want explicit string polynomials $Z_1$ and $Z_2$ satisfying the Bézout identity

$$ Z_1 V_1 + Z_2 V_2 = \gcd(V_1, V_2), $$

from which $\operatorname{lcm}(V_1, V_2)$ can be obtained.

We proceed by extending the Euclidean algorithm for string polynomials using the division algorithm of Exercise 17, carefully maintaining the required invariants.

1. Preliminaries

The division algorithm for string polynomials states that if $V_2 \neq 0$ and $U_1 V_1 = U_2 V_2$, then there exist unique string polynomials $Q$ and $R$ such that

$$ V_1 = Q V_2 + R, \qquad \deg(R) < \deg(V_2), $$

and moreover, by the right-left symmetry of the division algorithm,

$$ U_2 = U_1 Q + R', \qquad \deg(R') < \deg(U_1). $$

The uniqueness of $Q$ and $R$ ensures that the gcrd obtained by the Euclidean iteration is uniquely defined, even in the noncommutative string-polynomial setting.

2. Extended Euclidean algorithm for string polynomials

We introduce auxiliary string polynomials to maintain a Bézout identity and facilitate computation of the lclm. Initialize:

$$ v_1 \leftarrow V_1, \quad v_2 \leftarrow V_2, \quad u_1 \leftarrow U_1, \quad u_2 \leftarrow U_2, $$

and

$$ z_1 \leftarrow 1, \quad z_2 \leftarrow 0, \quad z_1' \leftarrow 0, \quad z_2' \leftarrow 1, $$

so that initially

$$ z_1 V_1 + z_2 V_2 = v_1, \quad z_1' V_1 + z_2' V_2 = v_2. $$

At each step, perform the division

$$ v_1 = Q v_2 + R, \qquad \deg(R) < \deg(v_2), $$

and update the auxiliary polynomials as

$$ (z_1, z_2, z_1', z_2') \leftarrow (z_1', z_2', z_1 - Q z_1', z_2 - Q z_2'). $$

Verification of the Bézout identity:

At each step,

$$ v_1 = Q v_2 + R \implies R = v_1 - Q v_2. $$

If we maintain

$$ v_1 = z_1 V_1 + z_2 V_2, \quad v_2 = z_1' V_1 + z_2' V_2, $$

then after the update,

$$ \begin{aligned} R &= v_1 - Q v_2 \ &= (z_1 V_1 + z_2 V_2) - Q (z_1' V_1 + z_2' V_2) \ &= (z_1 - Q z_1') V_1 + (z_2 - Q z_2') V_2, \end{aligned} $$

so the updated $(z_1, z_2, z_1', z_2')$ correctly represents the new remainder $R$ as a linear combination of $V_1$ and $V_2$. This confirms that the Bézout identity is maintained at each step.

3. Iteration and termination

Iterate the procedure:

$$ (v_1, v_2) \leftarrow (v_2, R), \qquad (z_1, z_2, z_1', z_2') \leftarrow (z_1', z_2', z_1 - Q z_1', z_2 - Q z_2'), $$

until $v_2 = 0$. Let the last nonzero remainder be $v_1$. Then:

$v_1$ is a common right divisor of $V_1$ and $V_2$, because $v_1$ divides both $V_1$ and $V_2$ on the right through the Euclidean iteration.
Any other common right divisor of $V_1$ and $V_2$ must divide $v_1$ on the right, by the standard argument of Euclid's algorithm applied to the string-polynomial division. Therefore $v_1 = \gcd(V_1, V_2)$ is the greatest common right divisor.

The corresponding auxiliary polynomials $z_1$ and $z_2$ at this stage satisfy

$$ z_1 V_1 + z_2 V_2 = \gcd(V_1, V_2), $$

providing the Bézout identity.

4. Least common left multiple

Let $G = \gcd(V_1, V_2) = v_1$ and the associated Bézout coefficients $Z_1 = z_1$, $Z_2 = z_2$. Define

$$ \operatorname{lcm}(V_1, V_2) := Z_1 V_1 = Z_2 V_2. $$

Verification that this is indeed the least common left multiple:

Common left multiple: By construction, $Z_1 V_1 = Z_2 V_2$, so it is a common left multiple.
Minimality: If $L$ is any other common left multiple, say $L = W_1 V_1 = W_2 V_2$, then using the Bézout identity

$$ G = z_1 V_1 + z_2 V_2, $$

we can write

$$ L = W_1 V_1 = W_1 (z_1 V_1 + z_2 V_2) = (W_1 z_1 + W_2 z_2) G, $$

showing that $L$ is a left multiple of $G$. Consequently, any common left multiple of $V_1$ and $V_2$ is a left multiple of $Z_1 V_1$, proving minimality. Therefore

$$ \operatorname{lcm}(V_1, V_2) = Z_1 V_1 = Z_2 V_2. $$

5. Algorithm summary

The complete extended Euclidean algorithm for string polynomials is:

Input: Nonzero string polynomials $V_1, V_2$ with a common left multiple.

Initialization:

$$ v_1 \leftarrow V_1, \quad v_2 \leftarrow V_2, \quad z_1 \leftarrow 1, \quad z_2 \leftarrow 0, \quad z_1' \leftarrow 0, \quad z_2' \leftarrow 1. $$

Iteration: While $v_2 \neq 0$:

Compute the quotient and remainder $Q, R$ such that $v_1 = Q v_2 + R$, $\deg(R) < \deg(v_2)$.
Update

$$ (v_1, v_2) \leftarrow (v_2, R), \quad (z_1, z_2, z_1', z_2') \leftarrow (z_1', z_2', z_1 - Q z_1', z_2 - Q z_2'). $$

Termination: When $v_2 = 0$, let

$$ \gcd(V_1, V_2) = v_1, \quad Z_1 = z_1, \quad Z_2 = z_2, \quad \operatorname{lcm}(V_1, V_2) = Z_1 V_1 = Z_2 V_2. $$

This algorithm terminates in a finite number of steps because the degrees of the remainders strictly decrease at each iteration. It produces both the greatest common right divisor and the least common left multiple, together with a Bézout identity.

6. Conclusion

By carefully maintaining the Bézout coefficients $(z_1, z_2, z_1', z_2')$ at each step, we have rigorously justified