The greatest common divisor may be defined and exists, more generally, for multivariate polynomials over a field or the ring of integers, and also over a unique factorization domain.
Conversely, most of the modern theory of polynomial GCD has been developed to satisfy the need for efficiency of computer algebra systems.
In the case of the integers, this indetermination has been settled by choosing, as the GCD, the unique one which is positive (there is another one, which is its opposite).
The proof of the validity of this algorithm relies on the fact that during the whole "while" loop, we have a = bq + r and deg(r) is a non-negative integer that decreases at each iteration.
In the imperative programming style, the same algorithm becomes, giving a name to each intermediate remainder: The sequence of the degrees of the ri is strictly decreasing.
Bézout's identity is a GCD related theorem, initially proved for the integers, which is valid for every principal ideal domain.
Another difference with Euclid's algorithm is that it also uses the quotient, denoted "quo", of the Euclidean division instead of only the remainder.
An interesting feature of this algorithm is that, when the coefficients of Bezout's identity are needed, one gets for free the quotient of the input polynomials by their GCD.
An important application of the extended GCD algorithm is that it allows one to compute division in algebraic field extensions.
The inverse of a non zero element a of L is the coefficient u in Bézout's identity au + fv = 1, which may be computed by extended GCD algorithm.
Firstly, their definition through determinants allows bounding, through Hadamard inequality, the size of the coefficients of the GCD.
Let us describe these matrices more precisely; Let pi = 0 for i < 0 or i > m, and qi = 0 for i < 0 or i > n. The Sylvester matrix is the (m + n) × (m + n)-matrix such that the coefficient of the i-th row and the j-th column is pm+j−i for j ≤ n and qj−i for j > n:[note 1]
As defined, the columns of the matrix Ti are the vectors of the coefficients of some polynomials belonging to the image of
If the degree of the GCD is greater than i, then Bézout's identity shows that every non zero polynomial in the image of
The vector space of these multiples has the dimension m + n − 2i and has a base of polynomials of pairwise different degrees, not smaller than i.
This implies that the submatrix of the m + n − 2i first rows of the column echelon form of Ti is the identity matrix and thus that si is not 0.
For univariate polynomials over the rational numbers, one may think that Euclid's algorithm is a convenient method for computing the GCD.
However, it involves simplifying a large number of fractions of integers, and the resulting algorithm is not efficient.
For this reason, methods have been designed to modify Euclid's algorithm for working only with polynomials over the integers.
In practice, it is not interesting, as the size of the coefficients grows exponentially with the degree of the input polynomials.
However it requires to compute a number of GCD's in Z, and therefore is not sufficiently efficient to be used in practice, especially when Z is itself a polynomial ring.
On the other hand, the proof of correctness of the algorithm is difficult, because it should take into account all the possibilities for the difference of degrees of two consecutive remainders.
The ri are the successive pseudo remainders in Z[X], the variables i and di are non negative integers, and the Greek letters denote elements in Z.
The functions deg() and rem() denote the degree of a polynomial and the remainder of the Euclidean division.
The subresultant pseudo-remainder sequence may be modified similarly, in which case the signs of the remainders coincide with those computed over the rationals.
If f and g are polynomials in F[x] for some finitely generated field F, the Euclidean Algorithm is the most natural way to compute their GCD.
However, modern computer algebra systems only use it if F is finite because of a phenomenon called intermediate expression swell.
Although degrees keep decreasing during the Euclidean algorithm, if F is not finite then the bit size of the polynomials can increase (sometimes dramatically) during the computations because repeated arithmetic operations in F tends to lead to larger expressions.
One can prove[3] that this works provided that one discards modular images with non-minimal degrees, and avoids ideals I modulo which a leading coefficient vanishes.
Note that this example could easily be handled by any method because the degrees were too small for expression swell to occur, but it illustrates that if two polynomials have GCD 1, then the modular algorithm is likely to terminate after a single ideal