WOLFRAM

Wolfram Language & System Documentation Center

ExtendedGCD[n1,n2,…]

gives the extended greatest common divisor of the integers ni.

Details
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Properties & Relations  
Neat Examples  
See Also
Tech Notes
Related Guides
Related Links
History
Cite this Page

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 all

Basic Examples  (2)

The extended greatest common divisor of 2 and 3:

Wolfram Language code: {g, {a, b}} = ExtendedGCD[2, 3]
Wolfram Language code: 2a + 3b == g

Compute the extended GCD of several integers:

Wolfram Language code: {g, {a, b, c}} = ExtendedGCD[6, 15, 30]
Wolfram Language code: 6a + 15b + 30c == g

Scope  (1)

ExtendedGCD threads element-wise over lists:

Wolfram Language code: ExtendedGCD[3, {5, 15}]

Properties & Relations  (1)

The first element of ExtendedGCD is the GCD:

Wolfram Language code: ExtendedGCD[6, 21]
Wolfram Language code: GCD[6, 21]

Neat Examples  (1)

Wolfram Language code: ArrayPlot[Table[Last[ExtendedGCD[m, n]], {m, 100}, {n, 100}], ColorFunction -> Hue]
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_2026_extendedgcd, author="Wolfram Research", title="{ExtendedGCD}", year="2003", howpublished="\url{https://reference.wolfram.com/language/ref/ExtendedGCD.html}", note=[Accessed: 12-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_extendedgcd, organization={Wolfram Research}, title={ExtendedGCD}, year={2003}, url={https://reference.wolfram.com/language/ref/ExtendedGCD.html}, note=[Accessed: 12-June-2026]}