text: Like for the integers, the Euclidean division of the polynomials may be computed by the long division algorithm. This algorithm is usually presented for paper-and-pencil computation, but it works well on computers when formalized as follows (note that the names of the variables correspond exactly to the regions of the paper sheet in a pencil-and-paper computation of long division). In the following computation "deg" stands for the degree of its argument (with the convention ), and "lc" stands for the leading coefficient, the coefficient of the highest degree of the variable.
  The proof of the validity of this algorithm relies on the fact that during the whole "while" loop, we have  and  is a non-negative integer that decreases at each iteration. Thus the proof of the validity of this algorithm also proves the validity of the Euclidean division.
  Euclid's algorithm
  As for the integers, the Euclidean division allows us to define Euclid's algorithm for computing  GCDs.
  Starting from two polynomials a and b, Euclid's algorithm consists of recursively replacing the pair  by  (where "" denotes the remainder of the Euclidean division, computed by the algorithm of the preceding section), until b = 0. The GCD is the last non zero remainder.
  Euclid's algorithm may be formalized in the recursive programming style as:
  In the imperative programming style, the same algorithm becomes, giving a name to each intermediate remainder: