XGCD

The extended Euclidean algorithm -- $(g, x, y)$ with $g = \gcd(a, b) = ax + by$.

FungrimXGCD↗Fungrim entry

XGCD(a, b) -> Tuple(g, x, y)Bezout coefficients alongside the gcd

Typed signatures

Type	Package	Applies
(integer, integer) -> tuple<integer, integer, integer>	analytic	always

Domain: Number theory

Examples

Basic #

$\gcd(240, 46) = 2 = 240\cdot(-9) + 46\cdot47$

live ↗

In$\mathrm{XGCD}(240, 46)$Out$(2,-9,47)$

About

Examples	1
Crosswalk	FungrimFungrim entry ×8

See also: GCD, ExtendedGCD