({{, (RefLink[ExtendedGCD, paclet:ref/ExtendedGCD])[(Subscript[n, 1]),(Subscript[n, 2]),…]
gives the extended greatest common divisor of the integers (Subscript[n, i]). }})

OpenersNotesSection(Spacer1)Details

Integer mathematical function, suitable for both symbolic and numerical manipulation.

(RefLink[ExtendedGCD, paclet:ref/ExtendedGCD])[(Subscript[n, 1]),(Subscript[n, 2]),…] returns a list {g,{(Subscript[r, 1]),(Subscript[r, 2]),…}} where g is (RefLink[GCD, paclet:ref/GCD])[(Subscript[n, 1]),(Subscript[n, 2]),…] and g=(Subscript[r, 1])(Subscript[n, 1])+(Subscript[r, 2])(Subscript[n, 2])+….

(RefLink[ExtendedGCD, paclet:ref/ExtendedGCD]) automatically threads over lists.

OpenersPrimaryExamplesSection(Spacer1)Examples  (5)

OpenersExampleSection0(Spacer1)Basic Examples  (2)

The extended greatest common divisor of 2 and 3:

{g,{a,b}}=ExtendedGCD[2, 3]

2a+3b==g

Compute the extended GCD of several integers:

{g,{a,b,c}}=ExtendedGCD[6,15,30]

6a+15b+30c==g

OpenersExampleSection1(Spacer1)Scope  (1)

(RefLink[ExtendedGCD, paclet:ref/ExtendedGCD]) threads element-wise over lists:

ExtendedGCD[3,{5,15}]

OpenersExampleSection2(Spacer1)Properties & Relations  (1)

The first element of (RefLink[ExtendedGCD, paclet:ref/ExtendedGCD]) is the (RefLink[GCD, paclet:ref/GCD]):

ExtendedGCD[6,21]

GCD[6,21]

OpenersExampleSection3(Spacer1)Neat Examples  (1)

ArrayPlot[Table[Last[ExtendedGCD[m,n]],{m,100},{n,100}],ColorFunction->Hue]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[GCD, paclet:ref/GCD])  ▪  (RefLink[Reduce, paclet:ref/Reduce])  ▪  (RefLink[HermiteDecomposition, paclet:ref/HermiteDecomposition])  ▪  (RefLink[SmithDecomposition, paclet:ref/SmithDecomposition])  ▪  (RefLink[PolynomialExtendedGCD, paclet:ref/PolynomialExtendedGCD])}})}})

({{DocumentationFooterIconsRelatedTutorial.png, ({{Tutorials}, {▪(RefLinkPlain[Integer and Number Theoretic Functions, paclet:tutorial/IntegerAndNumberTheoreticalFunctions])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Number Theoretic Functions, paclet:guide/NumberTheoreticFunctions])}})}})

({{(Spacer1), ({{(Spacer1)Related Links}, {(WebLink[DocumentationFooterIconsRelatedLinks-MathWorld.png(Spacer1)MathWorld, http://mathworld.wolfram.com/GreatestCommonDivisor.html])}, {(WebLink[DocumentationFooterIconsRelatedLinks-Functions.png(Spacer1)The Wolfram Functions Site, http://functions.wolfram.com/IntegerFunctions/ExtendedGCD/])}, {(WebLink[DocumentationFooterIconsRelatedLinks-NKS.png(Spacer1)NKS|Online, http://www.wolframscience.com/nksonline/index/search.cgi?SearchIndex=ExtendedGCD]) ((WebLink[A New Kind of Science, http://www.wolframscience.com/nksonline/]))}})}})