Greatest Common Divisor of Two Polynomials - Pseudo-remainder Sequences

Pseudo-remainder Sequences

In this section, we consider an integral domain Z (typically the ring Z of the integers) and its field of fractions Q (typically the field Q of the rational numbers). Given two polynomials A and B in the univariate polynomial ring Z, the Euclidean division (over Q) of A by B provides a quotient and a remainder which may not belong to Z.

For, if one applies Euclid's algorithm to

and

the successive remainders of Euclid's algorithm are

One sees that, despite the small degree and the small size of the coefficients of the input polynomials, one has to manipulate and simplify integer fractions of rather large size.

The pseudo-division has been introduced to allow a variant of Euclid's algorithm for which all remainders belong to Z.

If and and a≥b, the pseudo-remainder of the pseudo-division of A by B, denoted by prem(A,B) is

where lc(B) is the leading coefficient of B (the coefficient of Xb).

The pseudo-remainder of the pseudo-division of two polynomials in Z belongs always to Z.

A pseudo-remainder sequence is the sequence of the (pseudo) remainders r_i obtained by replacing the instruction

of Euclid's algorithm by

where α is an element of Z that divides exactly every coefficient of the numerator. Different choices of α give different pseudo-remainder sequences, which are described in the next subsections.

As the common divisors of two polynomials are not changed if the polynomials are multiplied by invertible constants (in Q), the last non zero term in a pseudo-remainder sequence is a GCD (in Q) of the input polynomials. Therefore pseudo-remainder sequences allows to compute GCD's in Q without introducing fractions in Q.