({{, (RefLink[PolynomialExtendedGCD, paclet:ref/PolynomialExtendedGCD])[(Subscript[poly, 1]),(Subscript[poly, 2]),x] 
gives the extended GCD of (Subscript[poly, 1]) and (Subscript[poly, 2]) treated as univariate polynomials in x.}, {, (RefLink[PolynomialExtendedGCD, paclet:ref/PolynomialExtendedGCD])[(Subscript[poly, 1]),(Subscript[poly, 2]),x,(RefLink[Modulus, paclet:ref/Modulus])->p] 
gives the extended GCD over the integers mod prime p.}})

OpenersPrimaryExamplesSection(Spacer1)Examples  (8)

OpenersExampleSection0(Spacer1)Basic Examples  (1)

Compute the extended GCD:

{f,g}={2x^5-2x,(x^2-1)^2};

{d,{a,b}}=PolynomialExtendedGCD[f,g,x]

The second part gives coefficients of a linear combination of polynomials that yields the GCD:

a f+b g==d//Expand

OpenersExampleSection1(Spacer1)Scope  (3)

Polynomials with numeric coefficients:

PolynomialExtendedGCD[(x-1)(x-2)^2,(x-1)(x^2-3),x]

Polynomials with symbolic coefficients:

PolynomialExtendedGCD[(x-a)(b x-c)^2,(x-a)(x^2-b c),x]

Relatively prime polynomials:

PolynomialExtendedGCD[a x^2+b x+c,x-r,x]

OpenersExampleSection2(Spacer1)Options  (2)

OpenersExampleSubsection0(Spacer1)Modulus  (2)

Extended GCD over the integers:

PolynomialExtendedGCD[(x-1)^2(x-2)^2,(x-1)(x^2-3),x]

Extended GCD over the integers modulo 2:

PolynomialExtendedGCD[(x-1)^2(x-2)^2,(x-1)(x^2-3),x,Modulus->2]

OpenersExampleSection3(Spacer1)Applications  (1)

Given polynomials a, b, and c, find polynomials f and g such that a f+b g==c:

a=(x-1)(x^2+7x-9);
b=(x-1)^2(x^3-5x+3);
c=(x-1)(x^2-7);

{d,{r,s}}=PolynomialExtendedGCD[a,b,x]

A solution exists if and only if c is divisible by d:

h=Cancel[c/d]

{f,g}=h{r,s}

a f+b g==c//Expand

OpenersExampleSection4(Spacer1)Properties & Relations  (1)

The extended GCD of f and g is {d,{r,s}}, such that d==GCD(f,g)  and f r+g s==d:

f=2a(x^2-1)^2(x^3-2);
g=4a(x-1)^3(x^2-3);

{d,{r,s}}=PolynomialExtendedGCD[f,g,x]

r f+s g==d//Expand

d is equal to (RefLink[PolynomialGCD, paclet:ref/PolynomialGCD])[f,g] up to a factor not containing x:

PolynomialGCD[f,g]

Cancel[d/%]

r and s are uniquely determined by the following (RefLink[Exponent, paclet:ref/Exponent]) conditions:

Exponent[r,x]<Exponent[g,x]-Exponent[d,x]

Exponent[s,x]<Exponent[f,x]-Exponent[d,x]

Use (RefLink[Cancel, paclet:ref/Cancel]) or (RefLink[PolynomialRemainder, paclet:ref/PolynomialRemainder]) to prove that d divides f and g:

Cancel[f/d]

PolynomialRemainder[g,d,x]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[PolynomialGCD, paclet:ref/PolynomialGCD])  ▪  (RefLink[ExtendedGCD, paclet:ref/ExtendedGCD])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Polynomial Division, paclet:guide/PolynomialDivision])}})}})