Computing a gcd in Q[x,y]  

f = 1 + 2x + 2x^2 + x^3 + x y + 2 x^2  y + 2 x^3  y + x^4  y

1 + 2 x + 2 x^2 + x^3 + x y + 2 x^2 y + 2 x^3 y + x^4 y

g = -y + x^3 * y - x * y^2 + x^4 * y^2

-y + x^3 y - x y^2 + x^4 y^2


extract gcd of coefficients

fcoeff = CoefficientList [f, y]

{1 + 2 x + 2 x^2 + x^3, x + 2 x^2 + 2 x^3 + x^4}

<< poliesGCD.m

a = GCDPolies [fcoeff[[1]], fcoeff[[2]], x]

{{{1 + 2 x + 2 x^2 + x^3, 1, 0}, {x + 2 x^2 + 2 x^3 + x^4, 0, 1}, {1 + 2 x + 2 x^2 + x^3, 1, 0}, {0, -x, 1}}, {1 + 2 x + 2 x^2 + x^3, 1, 0}}

MatrixForm [a [[1]]]

( 2 3 ) ... 2 x + x 1 0 0 -x 1

gcdfcoeff = PoliesExtendedGCD [fcoeff[[1]], fcoeff[[2]], x] [[1]]

1 + 2 x + 2 x^2 + x^3

fprimitiv = (fcoeff / gcdfcoeff) . {y^0, y^1}   

1 + ((x + 2 x^2 + 2 x^3 + x^4) y)/(1 + 2 x + 2 x^2 + x^3)

fprimitiv = Simplify [fprimitiv]

1 + x y

gcoeff = CoefficientList [g, y]

{0, -1 + x^3, -x + x^4}

a = GCDPolies [gcoeff[[2]], gcoeff[[3]], x]

{{{-1 + x^3, 1, 0}, {-x + x^4, 0, 1}, {-1 + x^3, 1, 0}, {0, -x, 1}}, {-1 + x^3, 1, 0}}

MatrixForm [a[[1]]]

( 3 ) -1 + x 1 0 ... 0 1 3 -1 + x 1 0 0 -x 1

gcdgcoeff = PoliesExtendedGCD [gcoeff[[2]], gcoeff[[3]], x] [[1]]

-1 + x^3

gprimitiv = (gcoeff / gcdgcoeff) . {y^0, y^1, y^2}   

y + ((-x + x^4) y^2)/(-1 + x^3)

gprimitiv = Simplify [gprimitiv]

y (1 + x y)

Compute the gcds of the extracted parts

MatrixForm [GCDPolies [gcdfcoeff, gcdgcoeff, x] [[1]]]

( ) ... - - - - + - 0 2 2 2 2

d1 = PoliesExtendedGCD [gcdfcoeff, gcdgcoeff, x] [[1]]

2 + 2 x + 2 x^2

Compute the gcds of the primitiv parts

MatrixForm [GCDPolies [fprimitiv, gprimitiv, y] [[1]]]

( 1 + x y 1 0 ) y (1 + x y) 0 1 1 + x y 1 0 0 -y 1

d2 = PoliesExtendedGCD [fprimitiv, gprimitiv, y] [[1]]

1 + x y

CoefficientList [d2, y]

{1, x}

so d2 is already primitive

DD = d1   * d2

(2 + 2 x + 2 x^2) (1 + x y)

Check

PolynomialGCD [f, g]

1 + x + x^2 + x y + x^2 y + x^3 y

Expand [DD]

2 + 2 x + 2 x^2 + 2 x y + 2 x^2 y + 2 x^3 y

Created by Mathematica  (April 10, 2007)