Euclidean division
Euclidean division of polynomials, which is used in Euclid's algorithm for computing GCDs, is very similar to Euclidean division of integers. Its existence is based on the following theorem: Given two univariate polynomials "a" and "b" ≠ 0 defined over a field, there exist two polynomials "q" (the "quotient") and "r" (the "remainder") which satisfy