TAOCP 4.6.1 Exercise 10

Let $S$ be a unique factorization domain.

taocpmathematicsalgorithmsvolume-2math-hard

Section 4.6.1: Division of Polynomials

Exercise 10. [M28] Prove that the polynomials over a unique factorization domain form a unique factorization domain. [Hint: Use the result of exercise 9 to help show that there is at most one kind of factorization possible.]

Verified: yes
Solve time: 1m47s

Setup

Let $S$ be a unique factorization domain. The domain $S[x]$ of all polynomials over $S$ is already known to be an integral domain, since property (i) of a unique factorization domain implies that the product of two nonzero polynomials is nonzero.

It remains to prove two assertions:

  1. Every nonzero polynomial in $S[x]$ is either a unit or can be factored into irreducible polynomials.
  2. Such a factorization is unique up to order and multiplication by units.

Exercise 7 shows that the units of $S[x]$ are exactly the units of $S$.

Throughout the proof, write each nonzero polynomial in the form

$$ u(x)=\operatorname{cont}(u)\cdot \operatorname{pp}(u(x)) $$

as in (3), where $\operatorname{pp}(u(x))$ is primitive.

Solution

Let $K$ be the field of fractions of $S$. Since $S\subseteq K$, every polynomial in $S[x]$ may also be regarded as a polynomial in $K[x]$.

Because $K$ is a field, the Euclidean algorithm for polynomials applies in $K[x]$; hence every nonconstant polynomial in $K[x]$ factors into irreducible polynomials, and such factorizations are unique up to units and order.

Existence of factorizations

Let $u(x)\neq0$ be a nonunit polynomial of $S[x]$.

By Lemma H,

$$ u(x)=c,f(x), $$

where $c=\operatorname{cont}(u)\in S$ and $f(x)=\operatorname{pp}(u(x))$ is primitive.

Factor $c$ in the unique factorization domain $S$:

$$ c=a,p_1p_2\cdots p_r, $$

where $a$ is a unit and the $p_i$ are primes of $S$.

Next regard $f(x)$ as a polynomial over $K$. Since $K[x]$ is a unique factorization domain,

$$ f(x)=b,g_1(x)\cdots g_t(x), $$

where $b\in K^\times$ and the $g_i(x)$ are irreducible in $K[x]$.

For each $g_i(x)$, multiply by a suitable nonzero element of $K$ so that the resulting polynomial has coefficients in $S$ and is primitive. Denote the resulting primitive polynomial by $h_i(x)$. Then

$$ g_i(x)=\alpha_i h_i(x), \qquad \alpha_i\in K^\times . $$

Hence

$$ f(x)=b\alpha_1\cdots\alpha_t,h_1(x)\cdots h_t(x). $$

Since $f(x)$ is primitive, equation (4) and repeated application of Lemma G imply that the product $h_1(x)\cdots h_t(x)$ is primitive. Therefore the content of the right-hand side must be a unit. Consequently

$$ b\alpha_1\cdots\alpha_t $$

belongs to $S$ and is a unit of $S$. Thus

$$ f(x)=u_0,h_1(x)\cdots h_t(x), $$

with $u_0$ a unit of $S$.

Each $h_i(x)$ is irreducible in $S[x]$. For if

$$ h_i(x)=r(x)s(x) $$

in $S[x]$, then the same factorization holds in $K[x]$; irreducibility of $g_i(x)$ in $K[x]$ implies that one of $r(x)$ or $s(x)$ is a unit of $K[x]$. Such a unit is a nonzero constant, hence belongs to $S$ and is a unit of $S[x]$.

Combining the factorization of $c$ with that of $f(x)$ gives

$$ u(x) = (a u_0), p_1\cdots p_r, h_1(x)\cdots h_t(x), $$

a factorization into irreducibles of $S[x]$.

Thus every nonzero nonunit polynomial factors into irreducibles.

Uniqueness of factorizations

Suppose

$$ u(x) = p_1\cdots p_r,h_1(x)\cdots h_t(x) = q_1\cdots q_s,k_1(x)\cdots k_m(x), $$

where the $p_i,q_j\in S$ are primes of $S$, and the $h_i(x),k_j(x)$ are primitive irreducible polynomials of positive degree.

Taking contents and using (4),

$$ \operatorname{cont}(u) = a,p_1\cdots p_r = b,q_1\cdots q_s, $$

where $a$ and $b$ are units of $S$.

Since $S$ is a unique factorization domain, uniqueness in $S$ implies $r=s$ and, after reordering, each $p_i$ differs from the corresponding $q_i$ by a unit factor.

After cancelling these constant irreducible factors, there remains

$$ h_1(x)\cdots h_t(x) = c,k_1(x)\cdots k_m(x), $$

where $c$ is a unit of $S$.

Viewed in $K[x]$, this is a factorization of the same polynomial into irreducibles. Since $K[x]$ is a unique factorization domain, $t=m$ and, after a permutation, each $h_i(x)$ is a unit multiple in $K[x]$ of the corresponding $k_i(x)$.

Let

$$ h_i(x)=\lambda_i k_{\pi(i)}(x), \qquad \lambda_i\in K^\times . $$

Both $h_i(x)$ and $k_{\pi(i)}(x)$ are primitive. By Lemma H, two primitive associates differ only by a unit of $S$. Therefore each $\lambda_i$ is a unit of $S$.

Hence the irreducible factors in the two factorizations agree up to order and multiplication by units of $S[x]$.

Therefore factorization in $S[x]$ is unique.

This completes the proof.

∎

Verification

Existence rests on three facts:

  1. Every polynomial has the decomposition (3) supplied by Lemma H.
  2. Primitive factors remain primitive under multiplication by Lemma G.
  3. Every irreducible factor over the fraction field $K$ can be scaled to a primitive polynomial over $S$, and such a primitive factor is irreducible in $S[x]$.

Uniqueness rests on two independent uniqueness theorems:

  1. Unique factorization of the content in $S$.
  2. Unique factorization of the primitive part in $K[x]$.

Exercise 9 supplies the key ingredient that primitive irreducible polynomials over $S$ remain irreducible over the fraction field and that primitive associates over $K[x]$ differ only by units of $S$. Consequently no second essentially different factorization can occur.

Notes

This theorem is commonly called Gauss's theorem on unique factorization for polynomial rings. Repeated application yields that polynomial rings in any finite number of variables over a unique factorization domain are themselves unique factorization domains.