text: If, on the other hand, the degree of the GCD is , then Bézout's identity again allows proving that the multiples of the GCD that have a degree lower than  are in the image of . The vector space of these multiples has the dimension  and has a base of polynomials of pairwise different degrees, not smaller than . This implies that the submatrix of the  first rows of the column echelon form of  is the identity matrix and thus that  is not 0. Thus  is a polynomial in the image of , which is a multiple of the GCD and has the same degree. It is thus a greatest common divisor.
  GCD and root finding
  Square-free factorization
  Most root-finding algorithms behave badly with polynomials that have multiple roots. It is therefore useful to detect and remove them before calling a root-finding algorithm. A GCD computation allows detection of the existence of multiple roots, since the multiple roots of a polynomial are the roots of the GCD of the polynomial and its derivative.
  After computing the GCD of the polynomial and its derivative, further GCD computations provide the complete square-free factorization of the polynomial, which is a factorization
  where, for each , the polynomial  either is 1 if  does not have any root of multiplicity  or is a square-free polynomial (that is a polynomial without multiple root) whose roots are exactly the roots of multiplicity  of  (see Yun's algorithm).
  Thus the square-free factorization reduces root-finding of a polynomial with multiple roots to root-finding of several square-free polynomials of lower degree. The square-free factorization is also the first step in most polynomial factorization algorithms.
  Sturm sequence
  The Sturm sequence of a polynomial with real coefficients is the sequence of the remainders provided by a variant of Euclid's algorithm applied to the polynomial and its derivative. For getting the Sturm sequence, one simply replaces the instruction