Definition 1 Let and be polynomials. If and have no non-trivial common factor, then they are said to be coprime. That is, and are coprime if is a constant polynomial whenever and .
Theorem 1 (Euclid's algorithm) Let , be polynomials. Then there exist polynomials , with or such that
Euclid's algorithm is really just long division. We are applying it
here to polynomials, where is the `quotient' and is the
Theorem 2 If and are coprime polynomials, then there exists polynomials and such that
This is a corollary of Euclid's algorithm, and is equivalent to the definition of coprimality.
Gihan Marasingha 2005-09-19