TAOCP 4.6.1 Exercise 9

Let $S$ be a unique factorization domain, and let $u(z),v(z)\in S[z]$ be primitive polynomials.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.1: Division of Polynomials

Exercise 9. [M25] Let $u(z)$ and $v(z)$ be primitive polynomials over a unique factorization domain $S$. Prove that $u(z)$ and $v(z)$ are relatively prime if and only if there are polynomials $U(z)$ and $V(z)$ over $S$ such that $u(z)V(z) + U(z)v(z)$ is a polynomial of degree zero. [Hint: Extend Algorithm E, as Algorithm 4.5.2A is extended in exercise 3.]

Verified: yes
Solve time: 6m26s

Solution

Let $S$ be a unique factorization domain, and let $u(z),v(z)\in S[z]$ be primitive polynomials. We are asked to prove the equivalence

$$ (u,v)=1 \quad\Longleftrightarrow\quad \exists, U(z),V(z)\in S[z] \text{ such that } u(z)V(z)+v(z)U(z) \text{ is a nonzero constant polynomial.} $$

Step 1: Definitions

A polynomial $f(z)\in S[z]$ is primitive if the greatest common divisor of its coefficients is a unit in $S$. Two polynomials $u$ and $v$ are relatively prime if their only common divisors in $S[z]$ are units.

Step 2: If $u(z)V(z)+v(z)U(z)$ is a constant, then $(u,v)=1$

Suppose there exist $U(z),V(z)\in S[z]$ and a constant $c\in S$, $c\neq 0$, such that

$$ u(z)V(z) + v(z)U(z) = c. $$

Let $d(z)$ be any common divisor of $u$ and $v$ in $S[z]$. Then $d(z)$ divides both $u(z)$ and $v(z)$, so it divides any $S[z]$-linear combination. In particular, $d(z)$ divides

$$ u(z)V(z) + v(z)U(z) = c. $$

Since $c\neq 0$ is constant, $d(z)$ must itself be a unit in $S$. Therefore, $u$ and $v$ have no non-unit common divisor, which shows that $(u,v)=1$.

Step 3: If $(u,v)=1$, then there exist $U(z),V(z)$ giving a constant

Assume $(u,v)=1$. We want $U(z),V(z)$ such that $uV+vU$ is constant. We proceed by extending Algorithm E (the Euclidean algorithm) to $S[z]$.

Step 3a: Euclidean algorithm for polynomials over a UFD

Let $u_0(z)=u(z)$, $v_0(z)=v(z)$. We define sequences $(u_i)$ and $(v_i)$ recursively as in Algorithm E:

  1. If $\deg(u_i)\ge \deg(v_i)$, perform polynomial division in the fraction field of $S$, obtaining

$$ u_i = q_i v_i + r_i, \quad \deg(r_i)<\deg(v_i), $$

where $q_i\in \text{Frac}(S)[z]$ and $r_i\in S[z]$ after clearing denominators. Let $r_i' = \text{primitive part of } r_i$. Then $r_i' \in S[z]$ is primitive. Set $u_{i+1}=v_i$, $v_{i+1}=r_i'$.

  1. Repeat until some remainder $v_n$ has degree zero.

Because $u$ and $v$ are relatively prime, the last nonzero remainder is a constant polynomial (up to units). Denote this constant by $c\in S$, $c\neq 0$.

Step 3b: Back-substitution to get $U$ and $V$

Each step in the Euclidean algorithm can be expressed as an $S[z]$-linear combination:

$$ r_i = u_i - q_i v_i. $$

By induction, each remainder $r_i$ can be written as

$$ r_i = u A_i + v B_i $$

for some $A_i,B_i\in S[z]$ (possibly after clearing denominators and adjusting by units, which is allowed since $S$ is a UFD). In particular, the last nonzero remainder $c$ can be written as

$$ c = u V + v U $$

for some $U,V\in S[z]$, where $c$ is a nonzero constant. The primitive property ensures that clearing denominators at each step yields polynomials still in $S[z]$.

Step 4: Conclusion

We have proved both directions:

  1. If there exist $U,V$ with $uV+vU$ constant, then $(u,v)=1$.
  2. If $(u,v)=1$, applying the Euclidean algorithm over $S[z]$ and using back-substitution produces $U,V$ with $uV+vU$ a nonzero constant.

Hence

$$ (u,v)=1 \quad\Longleftrightarrow\quad \exists,U,V\in S[z] : uV+vU \text{ is a constant}. $$

This completes the proof. ∎

This argument works for any unique factorization domain $S$ and relies on the primitive property and extension of the Euclidean algorithm, exactly as suggested in the exercise hint.