text: Pseudo-remainder sequences In this section, we consider an integral domain  (typically the ring  of the integers) and its field of fractions  (typically the field  of the rational numbers). Given two polynomials  and  in the univariate polynomial ring , the Euclidean division (over ) of  by  provides a quotient and a remainder which may not belong to .
  For, if one applies Euclid's algorithm to the following polynomials
  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  has been introduced to allow a variant of Euclid's algorithm for which all remainders belong to .
  If  and  and , the pseudo-remainder of the pseudo-division of  by , denoted by  is
  where  is the leading coefficient of  (the coefficient of ).
  The pseudo-remainder of the pseudo-division of two polynomials in  belongs always to .
  A pseudo-remainder sequence is the sequence of the (pseudo) remainders  obtained by replacing the instruction
  of Euclid's algorithm by
  where  is an element of  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 ), the last nonzero term in a pseudo-remainder sequence is a GCD (in ) of the input polynomials. Therefore, pseudo-remainder sequences allows computing GCD's in  without introducing fractions in .