text: The sequence of the degrees of the  is strictly decreasing. Thus after, at most,  steps, one get a null remainder, say . As  and  have the same divisors, the set of the common divisors is not changed by Euclid's algorithm and thus all pairs  have the same set of common divisors. The common divisors of  and  are thus the common divisors of  and 0. Thus  is a GCD of  and .
  This not only proves that Euclid's algorithm computes GCDs but also proves that GCDs exist.
  Bézout's identity and extended GCD algorithm
  Bézout's identity is a GCD related theorem, initially proved for the integers, which is valid for every principal ideal domain. In the case of the univariate polynomials over a field, it may be stated as follows.
  The interest of this result in the case of the polynomials is that there is an efficient algorithm to compute the polynomials  and , This algorithm differs from Euclid's algorithm by a few more computations done at each iteration of the loop. It is therefore called extended GCD algorithm. Another difference with Euclid's algorithm is that it also uses the quotient, denoted "quo", of the Euclidean division instead of only the remainder. This algorithm works as follows.