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 allclose all

Basic 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)

Wolfram Research (1988), ExtendedGCD, Wolfram Language function, https://reference.wolfram.com/language/ref/ExtendedGCD.html (updated 2003).

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: 21-February-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: 21-February-2025 ]}