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  =  2x² + 2    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  =  lu(a) normal(a) (12)

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

For R = $\mbox{${\mathbb Z}$}$ we will take normal(a) = | a |. For R = $\bf k$[x] we will take normal(a) = a/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

$$\Rightarrow$$ (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_nxⁿ + ^... + f₁x + f₀ be a univariate polynomial over R of positive degree. The content of f, denoted cont(f ) is the gcd of its coefficients f_n,..., f₁, f₀. By convention the content of a constant polynomial f₀ $\in$ R is normal(f₀). Observe that cont(f ) is uniquely defined in any case.

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

p  =  cont(f )pp(f ). (14)

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

cont(c f )  =  c cont(f )    and    pp(c f )  =  c 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 modp and g modp are not zero. Hence fg modp is not zero too. This shows that p cannot divide cont(fg). Finally we have proved that no primes divide cont(fg) and thus cont(fg) = 1. $\qedsymbol$

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

cont(fg)  =  cont(f ) cont(g)    and    pp(fg)  =  pp(f ) pp(g). (16)

Proof. Let h = pp(fg) and h ^* = pp(f ) pp(g). By Gauss Lemma, the polynomial h ^* is primitive. By definition of the content and the primitive part of a polynomial, we have

fg	=	cont(f ) pp(f ) cont(g) pp(g)
	=	cont(f ) cont(g) h * .

(17)

Then since h ^* is primitive, with Proposition 3, we get

cont(fg)	=	cont(cont(f ) cont(g) h * )
	=	cont(f ) cont(g).

(18)

$\qedsymbol$

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

Proof. See [vzGG99]. $\qedsymbol$

Corollary 2   Let R be $\mbox{${\mathbb Z}$}$ or a field. Then R[x₁,..., 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. cont(h) = gcd(cont(f ), cont(g)) in R.
3. pp(h) = gcd(pp(f ), pp(g)) in R[x].
4. h = gcd(cont(f ), cont(g)) gcd(pp(f ), pp(g))
5. h/lc(h) is the monic gcd of f and g in K[x].

Proof. See [vzGG99]. $\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(cont(f ), 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$$ (20)

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

b = gcd(lc(f ), lc(g)) (21)

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

$$\nu \in$$ (22)

Finally we obtain

$$\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₁,..., 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₁,..., 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.