ExtendedGCD

The GCD of a and b together with Bézout coefficients x, y such that a·x + b·y = GCD(a, b).

WikipediaExtended Euclidean algorithmWikidataQ1362750Wolfram LanguageExtendedGCD!Rosetta CodeModular inverse

ExtendedGCD(a, b) together with Bézout coefficients satisfying .

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 pair.
When , the coefficients reduce to .
compute-engine only accepts two.

Examples

See also: GCD