Relation between gcds in ${\mbox{${\mathbb{Q}}$}}[x]$ and ${\mbox{${\mathbb{Z}}$}}[x]$ . Polynomial gcds in non Euclidean domains.

Remark 3   The Euclidean Algorithm does not apply to ${\mbox{${\mathbb{Z}}$}}[x]$ since ${\mbox{${\mathbb{Z}}$}}[x]$ is not an Euclidean domain. However the concept of a polynomial gcd is well defined in ${\mbox{${\mathbb{Z}}$}}[x]$ since ${\mbox{${\mathbb{Z}}$}}[x]$ is a Unique Factorization Domain, as we shall review.

If we transport the computation of a gcd from ${\mbox{${\mathbb{Z}}$}}[x]$ to ${\mbox{${\mathbb{Q}}$}}[x]$ we should be careful. For instance with

$$f \ = \ 2 x^2 +2 \ \ \ \ {\rm and} \ \ \ \ g \ = \ 6x +2.$$ (11)

In ${\mbox{${\mathbb{Q}}$}}[x]$ their normalized gcd will be $1$ whereas their expected gcd in ${\mbox{${\mathbb{Z}}$}}[x]$ is 2.

Notation 1   Let $R$ be a commutative ring with identity element. Every element $a \in R$ can be written

$$a \ = \ {\rm lu}(a) \ {\rm normal}(a)$$ (12)

where ${\rm normal}(a)$ stands for a canonical representative of the class of the elements associate with $a$ and where ${\rm lu}(a)$ is a unit. Observe that $a$ is a unit iff ${\rm normal}(a)$ is $1$ .

For $R = {\mbox{${\mathbb{Z}}$}}$ we will take ${\rm normal}(a) = \mid a \mid$ . For $R = {\bf k}[x]$ we will take ${\rm normal}(a) = a / {\rm lc}(a)$ .

Remark 4   A nonzero nonunit $p \in R$ is reducible if there are two nonunits $c,d \in R$ such that $p = c \, d$ , otherwise $p$ is irreducible. Units are neither reducible nor irreducible. A nonzero nonunit $p \in R$ is prime if for every $c,d \in R$ we have we have

$$(p \ \mid \ cd) \ \ \ \ \Rightarrow \ \ \ \ (p \ \mid \ c \ \ {\rm or} \ \ p \ \mid \ d)$$ (13)

Observe that a prime is irreducible.

Assume from now on that $R$ is a Unique Factorization Domain (UFD). This means that $R$ is an integral domain such that

• every irreducible is a prime
• every nonzero nonunit $a \in R$ can be written as a product of irreducible elements in a unique way up to reordering and multiplication by units.

This leads to a natural formula for gcds, but not to an algorithm. However we assume that all gcds (for which we have an algorithm or not) are normalized. Hence we assume that gcds are uniquely defined.

Definition 3   Let $R$ be a UFD and $f = f_n x^n + \cdots + f_1 x + f_0$ be a univariate polynomial over $R$ of positive degree. The content of $f$ , denoted ${\rm cont}(f)$ is the gcd of its coefficients $f_n, \ldots, f_1, f_0$ . By convention the content of a constant polynomial $f_0 \in R$ is ${\rm normal}(f_0)$ . Observe that ${\rm cont}(f)$ is uniquely defined in any case.

The polynomial $f \in R[x]$ is primitive if ${\rm cont}(f) = 1$ . The primitive part of $f \in R[x]$ is the polynomial ${\rm pp}(f) \in R[x]$ such that

$$p \ = \ {\rm cont}(f) {\rm pp}(f).$$ (14)

Proposition 3   If $R$ is a UFD, for $f \in R[x]$ and $c \in R$ we have

$${\rm cont}(c \, f) \ = \ c \ {\rm cont}(f) \ \ \ \ {\rm and } \ \ \ \ {\rm pp}(c \, f) \ = \ c \ {\rm pp}(f)$$ (15)

Theorem 1 (Gauss Lemma)   If $R$ is a UFD, the product of two primitive polynomials in $R[x]$ is primitive.

Proof. Let $R$ be a UFD. Let $f,g \in R[x]$ be primitive. Let $p \in R$ be a prime. Then, the residue class ring $D = R / p$ is an integral domain. It follows (this is a classical result) that $D[x]$ is an integral domain too. By hypothesis $f \mod{p}$ and $g \mod{p}$ are not zero. Hence $f g \mod{p}$ is not zero too. This shows that $p$ cannot divide ${\rm cont}(fg)$ . Finally we have proved that no primes divide ${\rm cont}(fg)$ and thus ${\rm cont}(fg) = 1$ . $\qedsymbol$

Corollary 1   Let $R$ be a UFD. Let $f,g \in R[x]$ . Then we have

$${\rm cont}(f g) \ = \ {\rm cont}(f) \, {\rm cont}(g) \ \ \ \ {\rm and } \ \ \ \ {\rm pp}(f g) \ = \ {\rm pp}(f) \, {\rm pp}(g).$$ (16)

Proof. Let $h = {\rm pp}(f g)$ and $h^{\ast} = {\rm pp}(f)\, {\rm pp}(g)$ . By Gauss Lemma, the polynomial $h^{\ast}$ is primitive. By definition of the content and the primitive part of a polynomial, we have

$$\begin{array}{rcl} f g & = & {\rm cont}(f) \, {\rm pp}(f) \, ... ...\ & = & {\rm cont}(f) \, {\rm cont}(g) \, h^{\ast}. \end{array}$$ (17)

Then since $h^{\ast}$ is primitive, with Proposition 3, we get

$$\begin{array}{rcl} {\rm cont}(f g) & = & {\rm cont}( {\rm con... ...h^{\ast} ) \\ & = & {\rm cont}(f) \, {\rm cont}(g). \end{array}$$ (18)

$\qedsymbol$

Theorem 2 (Gauss)   If $R$ is a UFD, then so is $R[x]$ .

Proof. See [GG99]. $\qedsymbol$

Corollary 2   Let $R$ be ${\mbox{${\mathbb{Z}}$}}$ or a field. Then $R[x_1, \ldots, x_n]$ is a UFD.

Proof. This is a direct consequence of Theorem 2. $\qedsymbol$

Corollary 3   Let $R$ be a UFD with field of fractions $K$ . Let $f,g \in R[x]$ be univariate polynomials over $R$ and let $h$ be their normalized gcd in $R[x]$ . Then the following properties hold.

1. The prime elements of $R[x]$ are the primes of $R$ plus the primitive polynomials in $R[x]$ that are irreducible in $K[x]$ .
2. ${\rm cont}(h) = {\gcd}({\rm cont}(f), {\rm cont}(g))$ in $R$ .
3. ${\rm pp}(h) = {\gcd}({\rm pp}(f), {\rm pp}(g))$ in $R[x]$ .
4. $h = {\gcd}({\rm cont}(f), {\rm cont}(g)) \ {\gcd}({\rm pp}(f), {\rm pp}(g))$
5. $h / {\rm lc}(h)$ is the monic gcd of $f$ and $g$ in $K[x]$ .

Proof. See [GG99]. $\qedsymbol$

Remark 5   From Corollary 3 we can derive an algorithm for computing the normalized gcd $h$ of $f,g \in R[x]$ by means of a polynomial gcd computation in $K[x]$ and gcd computations in $R$ . We define

$$c = {\gcd}({\rm cont}(f), {\rm cont}(g))$$ (19)

To compute the primitive part of ${\gcd}_{R[x]}(f,g)$ we can assume that $f$ and $g$ are divided out by their contents. Let ${\nu}$ be the monic gcd of $f$ and $g$ in $K[x]$ . We have

$${\nu} \ = \ h / {\rm lc}(h)$$ (20)

Since $h$ divides $f$ and $g$ in $R[x]$ then ${\rm lc } (h)$ divides ${\rm lc}(f)$ and ${\rm lc}(g)$ in $R$ . Hence ${\rm lc } (h)$ divides ${\gcd}({\rm lc}(f), {\rm lc}(g))$ . We define

$$b = {\gcd}({\rm lc}(f), {\rm lc}(g))$$ (21)

Since $h = {\rm lc}(h) \ {\nu}$ lies in $R[x]$ and since ${\rm lc } (h)$ divides $b$ we have

$$b \, {\nu} \in R[x]$$ (22)

Finally we obtain

$$h \ = \ c \ \ {\rm pp}(b \, {\nu})$$ (23)

Remark 6   It follows from Corollary 3 and Remark 5 that if we have an algorithm for computing gcds in some UFD $R$ then we have an algorithm to compute gcds in $R[x_1, \ldots, x_n]$ . Of course this method based on the Euclidean Algorithm may not be the most efficient one.

In fact for computing gcds in ${\mbox{${\mathbb{Z}}$}}[x]$ (and more generally over ${\mbox{${\mathbb{Z}}$}}[x_1, \ldots, x_n]$ ) the modular methods (to be described shortly) are much more efficient than going through ${\mbox{${\mathbb{Q}}$}}[x]$ and the Euclidean Algorithm.

The simplest approach would be

• to chose a large prime $p$
• then to compute the gcd $\overline{h}$ of $f$ and $g$ in ${{\mbox{${\mathbb{Z}}$}}/{\langle p \rangle}}{\mbox{${\mathbb{Z}}$}}[x]$ (rather than ${\mbox{${\mathbb{Z}}$}}[x]$ )
• and to recover the gcd $h$ of $f$ and $g$ in ${\mbox{${\mathbb{Z}}$}}[x]$ from $\overline{h}$ .

This could work provided that

• $\overline{h}$ is the modular image of $h$ and that
• we have a reasonable bound for the coefficients of $h$ .

The next section introduces a powerful tool to control modular images of polynomial gcds.