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 modulo the prime p.
Details and Options
- PolynomialExtendedGCD takes the following options:
-
Method Automatic method to use Modulus 0 modulus to assume for integers
Examples
open all close allBasic Examples (2)
{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//ExpandCompute the extended GCD of polynomials with coefficients involving symbolic parameters:
PolynomialExtendedGCD[a(x + b) ^ 2, (x + a)(x + b), x]Scope (6)
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]PolynomialExtendedGCD[a x ^ 2 + b x + c, x - r, x]Polynomials with complex coefficients:
PolynomialExtendedGCD[(x - I)(x ^ 2 + 1), (x - 1)(x + I), x]Compute the extended GCD of polynomials over the integers modulo 3:
PolynomialExtendedGCD[(x - 1) ^ 2(x - 2) ^ 3, x ^ 3 - 1, x, Modulus -> 3]Compute the extended GCD of polynomials over a finite field:
ℱ = FiniteField[17, 3];PolynomialExtendedGCD[ℱ[1]x ^ 2 + ℱ[246]x + ℱ[4436], ℱ[3]x ^ 3 + ℱ[1771]x, x]Options (2)
Applications (1)
Given polynomials 
, 
, and 
, find polynomials 
and 
such that 
:
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 
is divisible by 
:
h = Cancel[c / d]{f, g} = h{r, s}a f + b g == c//ExpandProperties & Relations (1)
The extended GCD of 
and 
is {d,{r,s}}, such that 
and 
:
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//Expandd is equal to PolynomialGCD[f,g] up to a factor not containing x:
PolynomialGCD[f, g]Cancel[d / %]
and 
are uniquely determined by the following Exponent conditions:
Exponent[r, x] < Exponent[g, x] - Exponent[d, x]Exponent[s, x] < Exponent[f, x] - Exponent[d, x]Use Cancel or PolynomialRemainder to prove that d divides f and g:
Cancel[f / d]PolynomialRemainder[g, d, x]Text
Wolfram Research (2007), PolynomialExtendedGCD, Wolfram Language function, https://reference.wolfram.com/language/ref/PolynomialExtendedGCD.html (updated 2023).
CMS
Wolfram Language. 2007. "PolynomialExtendedGCD." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2023. https://reference.wolfram.com/language/ref/PolynomialExtendedGCD.html.
APA
Wolfram Language. (2007). PolynomialExtendedGCD. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/PolynomialExtendedGCD.html