- here we will consider polynomials from in one
variable with rational coefficients
- the degree of polynomial will be denoted by
- for two polynomials from for which , we define
their quotient and remainder as polynomials from
which satisfy
where

- as was the case for integers, the following identity for the greatest
common divisor (GCD) of polynomials holds
- Euclidean algorithm for calculating GCD of two polynomials with
rational coefficients
gcd := GCDPQ(a(x), b(x)) := [a, b are polynomials in Q[x] algorithms used: deg(a) - degree of polynomial a rem(a, b) - remainder after dividing polynomial a by polynomial b] 1. if deg(a) < deg(b) then r := a a := b b := r fi 2. while b != 0 do r := rem(a, b) a := b b := r do 3. return a

- this algorithm requires many greatest common divisor calculations
of two integers when performing calculations with rational numbers
and frequently, the integers can become rather large
- these calculations are time consuming so the algorithm is not so
efficient
- we can avoid calculations with rational numbers by doing the
computations in the domain of polynomials with integer coefficients

Richard Liska