--- title: "PolynomialExtendedGCD" language: "en" type: "Symbol" summary: "PolynomialExtendedGCD[poly1, poly2, x] gives the extended GCD of poly1 and poly2 treated as univariate polynomials in x. PolynomialExtendedGCD[poly1, poly2, x, Modulus -> p] gives the extended GCD over the integers modulo the prime p." keywords: - Aryabhatta's identity - Bezout identity - Euclidean algorithm - extended greatest common divisor - polynomial Diophantine equations - polynomial extended GCD - gcdex canonical_url: "https://reference.wolfram.com/language/ref/PolynomialExtendedGCD.html" source: "Wolfram Language Documentation" related_guides: - title: "Polynomial Division" link: "https://reference.wolfram.com/language/guide/PolynomialDivision.en.md" - title: "Finite Fields" link: "https://reference.wolfram.com/language/guide/FiniteFields.en.md" related_functions: - title: "PolynomialGCD" link: "https://reference.wolfram.com/language/ref/PolynomialGCD.en.md" - title: "ExtendedGCD" link: "https://reference.wolfram.com/language/ref/ExtendedGCD.en.md" - title: "FiniteField" link: "https://reference.wolfram.com/language/ref/FiniteField.en.md" --- # PolynomialExtendedGCD PolynomialExtendedGCD[poly1, poly2, x] gives the extended GCD of poly1 and poly2 treated as univariate polynomials in x. PolynomialExtendedGCD[poly1, poly2, x, Modulus -> p] 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 (12) ### Basic Examples (2) Compute the extended GCD: ```wl In[1]:= {f, g} = {2x ^ 5 - 2x, (x ^ 2 - 1) ^ 2}; In[2]:= {d, {a, b}} = PolynomialExtendedGCD[f, g, x] Out[2]= {-1 + x^2, {(x/4), (1/4) (-4 - 2 x^2)}} ``` The second part gives coefficients of a linear combination of polynomials that yields the GCD: ```wl In[3]:= a f + b g == d//Expand Out[3]= True ``` --- Compute the extended GCD of polynomials with coefficients involving symbolic parameters: ```wl In[1]:= PolynomialExtendedGCD[a(x + b) ^ 2, (x + a)(x + b), x] Out[1]= {b + x, {-(1/a (a - b)), (1/a - b)}} ``` ### Scope (6) Polynomials with numeric coefficients: ```wl In[1]:= PolynomialExtendedGCD[(x - 1)(x - 2) ^ 2, (x - 1)(x ^ 2 - 3), x] Out[1]= {-1 + x, {7 + 4 x, 9 - 4 x}} ``` --- Polynomials with symbolic coefficients: ```wl In[1]:= PolynomialExtendedGCD[(x - a)(b x - c) ^ 2, (x - a)(x ^ 2 - b c), x] Out[1]= {-a + x, {(b^3 c + c^2 + 2 b c x/b^6 c^2 - 2 b^3 c^3 + c^4), (-b^5 c + 3 b^2 c^2 - 2 b^3 c x/b^6 c^2 - 2 b^3 c^3 + c^4)}} ``` --- Relatively prime polynomials: ```wl In[1]:= PolynomialExtendedGCD[a x ^ 2 + b x + c, x - r, x] Out[1]= {1, {(1/c + b r + a r^2), (-b - a r - a x/c + b r + a r^2)}} ``` --- Polynomials with complex coefficients: ```wl In[1]:= PolynomialExtendedGCD[(x - I)(x ^ 2 + 1), (x - 1)(x + I), x] Out[1]= {I + x, {(I/2), (1/2) I ((-1 + 2 I) - x)}} ``` --- Compute the extended GCD of polynomials over the integers modulo 3: ```wl In[1]:= PolynomialExtendedGCD[(x - 1) ^ 2(x - 2) ^ 3, x ^ 3 - 1, x, Modulus -> 3] Out[1]= {1 + x + x^2, {2, 1 + x + x^2}} ``` --- Compute the extended GCD of polynomials over a finite field: ```wl In[1]:= ℱ = FiniteField[17, 3]; In[2]:= PolynomialExtendedGCD[ℱ[1]x ^ 2 + ℱ[246]x + ℱ[4436], ℱ[3]x ^ 3 + ℱ[1771]x, x] Out[2]= [image] ``` ### Options (2) #### Modulus (2) Extended GCD over the integers: ```wl In[1]:= PolynomialExtendedGCD[(x - 1) ^ 2(x - 2) ^ 2, (x - 1)(x ^ 2 - 3), x] Out[1]= {-1 + x, {(1/2) (19 + 11 x), (1/2) (-26 + 36 x - 11 x^2)}} ``` --- Extended GCD over the integers modulo 2: ```wl In[1]:= PolynomialExtendedGCD[(x - 1) ^ 2(x - 2) ^ 2, (x - 1)(x ^ 2 - 3), x, Modulus -> 2] Out[1]= {1 + x^2, {1, 1 + x}} ``` ### Applications (1) Given polynomials $a$, $b$, and $c$, find polynomials $f$ and $g$ such that $a f+b g=c$ : ```wl In[1]:= a = (x - 1)(x ^ 2 + 7x - 9); b = (x - 1) ^ 2(x ^ 3 - 5x + 3); c = (x - 1)(x ^ 2 - 7); In[2]:= {d, {r, s}} = PolynomialExtendedGCD[a, b, x] Out[2]= {-1 + x, {(1/579) (1244 - 2360 x + 53 x^2 + 484 x^3), (1/579) (-3925 - 484 x)}} ``` A solution exists if and only if $c$ is divisible by $d$ : ```wl In[3]:= h = Cancel[c / d] Out[3]= -7 + x^2 In[4]:= {f, g} = h{r, s} Out[4]= {(1/579) (-7 + x^2) (1244 - 2360 x + 53 x^2 + 484 x^3), (1/579) (-3925 - 484 x) (-7 + x^2)} In[5]:= a f + b g == c//Expand Out[5]= True ``` ### Properties & Relations (1) The extended GCD of $f$ and $g$ is ``{d, {r, s}}``, such that $d=\text{GCD}(f,g)$ and $f r+g s=d$ : ```wl In[1]:= f = 2a(x ^ 2 - 1) ^ 2(x ^ 3 - 2); g = 4a(x - 1) ^ 3(x ^ 2 - 3); In[2]:= {d, {r, s}} = PolynomialExtendedGCD[f, g, x] Out[2]= {1 - 2 x + x^2, {-(166 - 32 x - 42 x^2/736 a), -(-12 + 188 x + 224 x^2 + 158 x^3 + 42 x^4/1472 a)}} In[3]:= r f + s g == d//Expand Out[3]= True ``` ``d`` is equal to ``PolynomialGCD[f, g]`` up to a factor not containing ``x`` : ```wl In[4]:= PolynomialGCD[f, g] Out[4]= 2 a (-1 + x)^2 In[5]:= Cancel[d / %] Out[5]= (1/2 a) ``` $$r$$`` and ``$$s$$ are uniquely determined by the following ``Exponent`` conditions: ```wl In[6]:= Exponent[r, x] < Exponent[g, x] - Exponent[d, x] Out[6]= True In[7]:= Exponent[s, x] < Exponent[f, x] - Exponent[d, x] Out[7]= True ``` Use ``Cancel`` or ``PolynomialRemainder`` to prove that ``d`` divides ``f`` and ``g`` : ```wl In[8]:= Cancel[f / d] Out[8]= 2 a (1 + x)^2 (-2 + x^3) In[9]:= PolynomialRemainder[g, d, x] Out[9]= 0 ``` ## See Also * [`PolynomialGCD`](https://reference.wolfram.com/language/ref/PolynomialGCD.en.md) * [`ExtendedGCD`](https://reference.wolfram.com/language/ref/ExtendedGCD.en.md) * [`FiniteField`](https://reference.wolfram.com/language/ref/FiniteField.en.md) ## Related Guides * [Polynomial Division](https://reference.wolfram.com/language/guide/PolynomialDivision.en.md) * [Finite Fields](https://reference.wolfram.com/language/guide/FiniteFields.en.md) ## History * [Introduced in 2007 (6.0)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn60.en.md) \| [Updated in 2023 (13.3)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn133.en.md)