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 remainder'.

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