WOLFRAM

Wolfram Language & System Documentation Center

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.

Examples  
Basic Examples  
Scope  
Options  
Modulus  
Applications  
Properties & Relations  
See Also
Related Guides
History
Cite this Page

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.

Examples

open all close all

Basic Examples  (2)

Compute the extended GCD:

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

Compute the extended GCD of polynomials with coefficients involving symbolic parameters:

Scope  (6)

Polynomials with numeric coefficients:

Polynomials with symbolic coefficients:

Relatively prime polynomials:

Polynomials with complex coefficients:

Compute the extended GCD of polynomials over the integers modulo 3:

Compute the extended GCD of polynomials over a finite field:

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:

Wolfram Research (2007), PolynomialExtendedGCD, Wolfram Language function, https://reference.wolfram.com/language/ref/PolynomialExtendedGCD.html (updated 2023).

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

BibTeX

@misc{reference.wolfram_2025_polynomialextendedgcd, author="Wolfram Research", title="{PolynomialExtendedGCD}", year="2023", howpublished="\url{https://reference.wolfram.com/language/ref/PolynomialExtendedGCD.html}", note=[Accessed: 16-August-2025]}

BibLaTeX

@online{reference.wolfram_2025_polynomialextendedgcd, organization={Wolfram Research}, title={PolynomialExtendedGCD}, year={2023}, url={https://reference.wolfram.com/language/ref/PolynomialExtendedGCD.html}, note=[Accessed: 16-August-2025]}