ExtendedGCD [n1,n2,…]
gives the extended greatest common divisor of the integers ni.
ExtendedGCD
ExtendedGCD [n1,n2,…]
gives the extended greatest common divisor of the integers ni.
Details
- Integer mathematical function, suitable for both symbolic and numerical manipulation.
- ExtendedGCD [n1,n2,…] returns a list {g,{r_(1),r_(2),...}} where g is GCD [n1,n2,…] and g=r_(1)n_(1)+r_(2)n_(2)+....
- ExtendedGCD automatically threads over lists.
Examples
open all close allBasic Examples (2)
The extended greatest common divisor of 2 and 3:
Compute the extended GCD of several integers:
Scope (1)
ExtendedGCD threads element-wise over lists:
Properties & Relations (1)
The first element of ExtendedGCD is the GCD :
Neat Examples (1)
See Also
GCD Reduce HermiteDecomposition SmithDecomposition PolynomialExtendedGCD
Function Repository: HalfGCD
Tech Notes
Related Guides
Related Links
History
Introduced in 1988 (1.0) | Updated in 2003 (5.0)
Text
Wolfram Research (1988), ExtendedGCD, Wolfram Language function, https://reference.wolfram.com/language/ref/ExtendedGCD.html (updated 2003).
CMS
Wolfram Language. 1988. "ExtendedGCD." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2003. https://reference.wolfram.com/language/ref/ExtendedGCD.html.
APA
Wolfram Language. (1988). ExtendedGCD. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/ExtendedGCD.html
BibTeX
@misc{reference.wolfram_2025_extendedgcd, author="Wolfram Research", title="{ExtendedGCD}", year="2003", howpublished="\url{https://reference.wolfram.com/language/ref/ExtendedGCD.html}", note=[Accessed: 05-December-2025]}
BibLaTeX
@online{reference.wolfram_2025_extendedgcd, organization={Wolfram Research}, title={ExtendedGCD}, year={2003}, url={https://reference.wolfram.com/language/ref/ExtendedGCD.html}, note=[Accessed: 05-December-2025]}