PolynomialExtendedGCD

PolynomialExtendedGCD[poly1,poly2,x]

gives the extended GCD of poly1 and poly2 treated as univariate polynomials in x.

PolynomialExtendedGCD[poly1,poly2,x,Modulusp]

gives the extended GCD over the integers mod prime p.

Examples

open allclose all

Basic Examples  (1)

Compute the extended GCD:

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

Scope  (3)

Polynomials with numeric coefficients:

Polynomials with symbolic coefficients:

Relatively prime polynomials:

Options  (2)

Modulus  (2)

Extended GCD over the integers:

Extended GCD over the integers modulo 2:

Applications  (1)

Given polynomials , , and , find polynomials and such that :

A solution exists if and only if is divisible by :

Properties & Relations  (1)

The extended GCD of and is {d,{r,s}}, such that and :

d is equal to PolynomialGCD[f,g] up to a factor not containing x:

r and s are uniquely determined by the following Exponent conditions:

Use Cancel or PolynomialRemainder to prove that d divides f and g:

Introduced in 2007
 (6.0)