GCD of polynomials with rational coefficients

 

• 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

 
• Example of GCD in Q[x]