# Relation between gcds in and . Polynomial gcds in non Euclidean domains.

Remark 3   The Euclidean Algorithm does not apply to since is not an Euclidean domain. However the concept of a polynomial gcd is well defined in since is a Unique Factorization Domain, as we shall review.

If we transport the computation of a gcd from to we should be careful. For instance with

 (11)

In their normalized gcd will be whereas their expected gcd in is 2.

Notation 1   Let be a commutative ring with identity element. Every element can be written

 (12)

where stands for a canonical representative of the class of the elements associate with and where is a unit. Observe that is a unit iff is .

For we will take . For we will take .

Remark 4   A nonzero nonunit is reducible if there are two nonunits such that , otherwise is irreducible. Units are neither reducible nor irreducible. A nonzero nonunit is prime if for every we have we have

 (13)

Observe that a prime is irreducible.

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

• every irreducible is a prime
• every nonzero nonunit 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 be a UFD and be a univariate polynomial over of positive degree. The content of , denoted is the gcd of its coefficients . By convention the content of a constant polynomial is . Observe that is uniquely defined in any case.

The polynomial is primitive if . The primitive part of is the polynomial such that

 (14)

Proposition 3   If is a UFD, for and we have

 (15)

Theorem 1 (Gauss Lemma)   If is a UFD, the product of two primitive polynomials in is primitive.

Proof. Let be a UFD. Let be primitive. Let be a prime. Then, the residue class ring is an integral domain. It follows (this is a classical result) that is an integral domain too. By hypothesis and are not zero. Hence is not zero too. This shows that cannot divide . Finally we have proved that no primes divide and thus .

Corollary 1   Let be a UFD. Let . Then we have

 (16)

Proof. Let and . By Gauss Lemma, the polynomial is primitive. By definition of the content and the primitive part of a polynomial, we have

 (17)

Then since is primitive, with Proposition 3, we get

 (18)

Theorem 2 (Gauss)   If is a UFD, then so is .

Proof. See [GG99].

Corollary 2   Let be or a field. Then is a UFD.

Proof. This is a direct consequence of Theorem 2.

Corollary 3   Let be a UFD with field of fractions . Let be univariate polynomials over and let be their normalized gcd in . Then the following properties hold.
1. The prime elements of are the primes of plus the primitive polynomials in that are irreducible in .
2. in .
3. in .
4. is the monic gcd of and in .

Proof. See [GG99].

Remark 5   From Corollary 3 we can derive an algorithm for computing the normalized gcd of by means of a polynomial gcd computation in and gcd computations in . We define

 (19)

To compute the primitive part of we can assume that and are divided out by their contents. Let be the monic gcd of and in . We have

 (20)

Since divides and in then divides and in . Hence divides . We define

 (21)

Since lies in and since divides we have

 (22)

Finally we obtain

 (23)

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

In fact for computing gcds in (and more generally over ) the modular methods (to be described shortly) are much more efficient than going through and the Euclidean Algorithm.

The simplest approach would be

• to chose a large prime
• then to compute the gcd of and in (rather than )
• and to recover the gcd of and in from .
This could work provided that
• is the modular image of and that
• we have a reasonable bound for the coefficients of .
The next section introduces a powerful tool to control modular images of polynomial gcds.

Marc Moreno Maza
2008-01-07