This is documentation for Mathematica 3, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.2)
 Documentation / Mathematica / Add-ons / Standard Packages / Algebra  /


PolynomialExtendedGCD gives the extended greatest common divisor for two univariate polynomials. The Mathematica kernel has the functions GCD and ExtendedGCD for integers, and the function PolynomialGCD for multivariate polynomials over the rationals. The function defined in this package works not only for polynomials over the rationals, but also for polynomials over the integers mod prime , and for polynomials with coefficients in a finite field defined by the package Algebra`FiniteFields`.
In a Euclidean domain, such as addition and multiplication on the integers, or addition and multiplication on univariate polynomials with coefficients in some field, it is possible to write the gcd of two elements as a linear combination of the two elements. The extended gcd gives the coefficients of the linear combination. PolynomialExtendedGCD[


] gives the list



where is the greatest common divisor of and , and and are polynomials such that r



Polynomial greatest common divisor.

  • This loads the package.
  • In[1]:= <<Algebra`PolynomialExtendedGCD`

  • Here is an example over the integers mod 7.
  • In[2]:= PolynomialExtendedGCD[x^2 + 2 x + 1,
    Expand[(x + 1)(x + 2)], Modulus->7]


  • Here is the same example over the rationals.
  • In[3]:= PolynomialExtendedGCD[x^2 + 2 x + 1,
    Expand[(x + 1)(x + 2)]]


  • Load the Algebra`FiniteFields` package.
  • In[4]:= <<Algebra`FiniteFields`

  • Here is the example over the field GF[7].
  • In[5]:= PolynomialExtendedGCD[
    x^2 + GF[7][{2}] x + GF[7][{1}],
    Expand[(x + GF[7][{1}])(x + GF[7][{2}])]]


  • Note that the kernel function PolynomialGCD does not work for polynomials over finite fields. Apply First to the result of PolynomialExtendedGCD instead.
  • In[6]:= PolynomialGCD[x^2 + GF[7][{2}] x + GF[7][{1}],
    Expand[(x + GF[7][{1}])(x + GF[7][{2}])]]


  • Here the polynomial coefficients are Gaussian integers.
  • In[7]:= PolynomialExtendedGCD[
    Expand[ ((12+I) z^2 + 7 z + I) (I z + 3)],
    Expand[ ((9+2I) z + (3+I)) ((3I)z + 9)]