Built-in Mathematica Symbol

PolynomialExtendedGCD

PolynomialExtendedGCD[poly₁, poly₂, x]
gives the extended GCD of poly₁ and poly₂ treated as univariate polynomials in x.

PolynomialExtendedGCD[poly₁, poly₂, x, Modulus->p]
gives the extended GCD over the integers mod prime p.

Compute the extended GCD:

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

Compute the extended GCD:

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

Polynomials with numeric coefficients:

Polynomials with symbolic coefficients:

Relatively prime polynomials:

Extended GCD over the integers:

Extended GCD over the integers modulo 2:

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

c:

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

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

d:

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: