ExtendedGCD

The GCD of the arguments together with Bézout coefficients x₁, x₂, … such that a₁·x₁ + a₂·x₂ + … = GCD(a₁, a₂, …).

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaExtended Euclidean algorithm↗WikidataQ1362750↗Wolfram LanguageExtendedGCD!↗Rosetta CodeModular inverse↗

ExtendedGCD(a, b)$\gcd(a,b)$ together with Bézout coefficients $x,y$ satisfying $ax+by=\gcd(a,b)$.

SageMathxgcd(a, b)Oscarcollect(gcdx(ZZ(a), ZZ(b)))Juliacollect(gcdx(ZZ(a), ZZ(b)))Rustextended_gcd(a, b)

ExtendedGCD(a, b, c, …)$\gcd$ of any number of arguments, together with one Bézout coefficient per argument, folded pairwise from the two-argument case.

Typed signatures

Type	Package	Applies
(integer, integer) -> tuple<integer, integer, integer>	compute-engine	always
(number, number*) -> tuple	number-theoryreplaces compute-engine	always

Domain: Number theory

Details

• Implements the extended Euclidean algorithm, the standard way to compute modular inverses. See PowerMod.
• The coefficients are not unique; the algorithm returns one particular solution, by folding the two-argument case pairwise across the arguments left to right.
• When $a=0$, the coefficients reduce to $x=0,\,y=1$.

Examples

30 more kept as data, checked against the oracles

Basic #

live ↗

In$\mathrm{ExtendedGCD}(2, 3)$Out$(1,-1,1)$

live ↗

In$\mathrm{ExtendedGCD}(12, 18)$Out$(6,-1,1)$

live ↗

In$\mathrm{ExtendedGCD}(3, 5)$Out$(1,2,-1)$

Scope #

Any number of arguments: folding pairwise, $6\times(-2)+15\times1+30\times0=3=\gcd(6,15,30)$

live ↗

In$\mathrm{ExtendedGCD}(6, 15, 30)$Out$(3,-2,1,0)$

Gaussian integers, by Euclid with the rounded quotient

live ↗

In$\mathrm{ExtendedGCD}(7+2i, 3-5i)$Out$(1,-1-2i,-2+2i)$

Negative arguments: $-12+18=6$

live ↗

In$\mathrm{ExtendedGCD}(-12, 18)$Out$(6,1,1)$

Big integers; the coefficients stay minimal, $|x|<b$ and $|y|<a$

live ↗

In$\mathrm{ExtendedGCD}(2^{100}, 3^{50})$Out$(1,208\,475\,958\,620\,489\,751\,737\,959,-368\,122\,879\,029\,235\,364\,752\,383\,564\,167)$

Three arguments: $4\cdot4-6\cdot4+9=1$

live ↗

In$\mathrm{ExtendedGCD}(4, 6, 9)$Out$(1,4,-4,1)$

Listable: threads over a list

live ↗

In$\mathrm{ExtendedGCD}(3, \bigl\lbrack5, 15\bigr\rbrack)$Out$\bigl\lbrack(1,2,-1), (3,1,0)\bigr\rbrack$

Applications #

The modular inverse of 3 mod 11 is 4, since $3\times4\equiv1\pmod{11}$

live ↗

In$\mathrm{ExtendedGCD}(3, 11)$Out$(1,4,-1)$

Properties #

Confirms the coefficients above satisfy $2x+3y=\gcd(2,3)$ with $x=-1,\,y=1$

live ↗

In$-2×1+3×1$Out$1$

live ↗

In$\mathrm{ExtendedGCD}(6, 21)$Out$(3,-3,1)$

Possible issues #

Bézout coefficients when $a=0$: $0\times0+5\times1=5$

live ↗

In$\mathrm{ExtendedGCD}(0, 5)$Out$(5,0,1)$

About

Examples	43
Checked against	Wolfram Language 3 agree40 differSageMath 13 agree26 differSymPy 30 agree9 differmathlib4 11 agree1 differ2 errorOscar 11 agreeJulia 12 agree26 errorRust 12 agree1 differ1 errormpmath 1 agree
Crosswalk	WikipediaWikidataWolfram LanguageSageMathOscarJuliaRustRosetta Code

Implementation

mappedoscarpackages/oracle/src/mappings.ts

mappedwolframpackages/oracle/src/mappings.ts

Shape difference, not a value one: Wolfram's ExtendedGCD returns {g, {s, t}}, nested; ours returns the flat Tuple(g, s, t) compute-engine's own Tuple head calls for. The Bezout coefficients also aren't unique, so an occasional case lands on another valid (s, t) pair than Wolfram's Euclid would pick; ours still satisfies sa + tb = g.

mappedsympypackages/oracle/src/mappings.ts

SymPy's gcdex returns (s, t, g), a different order from our (g, s, t); the template only reorders the three. The Bezout pair is whichever the Euclidean algorithm reaches, and its sign convention for a negative argument is SymPy's own.

mappedsympypackages/oracle/src/mappings.ts

SymPy's gcdex takes two arguments and has no n-ary form; folding it pairwise would test our fold against itself, so the three-argument call is left unmapped.

mappedsagepackages/oracle/src/mappings.ts

mappedjuliapackages/oracle/src/mappings.ts

mappedrustpackages/oracle/src/mappings.ts

Bézout coefficients are the algorithm's choice among many, so a pair can differ from ours.

mappedmathlib4packages/oracle/src/mappings.ts

Int.gcd with its Bezout coefficients Int.gcdA and Int.gcdB, as a flat list [g, s, t] (a Lean tuple prints nested); the pair is whichever the Euclidean algorithm reaches, which need not be the one ours picks.

See also: GCD