Find Bézout coefficients with xgcd

xgcd(a, b) uses the extended Euclidean algorithm to find the greatest common divisor of two integers together with coefficients that express that divisor as a linear combination of the inputs. In other words, it finds values g, x, and y such that a*x + b*y = g, where g is the gcd of a and b.

Why the extended result is useful

The ordinary gcd function answers how large the common divisor is. Xgcd additionally supplies the coefficients needed to solve linear Diophantine equations and find modular inverses. For example, if the gcd of a and a modulus m is 1, the coefficient of a can be reduced modulo m to obtain an inverse; invmod provides that direct modular-inverse task.

Example

For inputs 30 and 18, the gcd is 6, and xgcd supplies coefficients satisfying 30*x + 18*y = 6. Those coefficients are not necessarily unique, but any returned pair proves the identity. Use mod to bring an inverse or coefficient into a preferred non-negative residue range, and lcm when the least common multiple is needed instead.

Input caveats

Use integer inputs for the standard number-theory interpretation. Signs can affect the reported coefficients even though gcd is conventionally non-negative. If both inputs are zero, the usual Bézout identity is degenerate, so handle that case explicitly. Xgcd is not a replacement for divide when ordinary numeric division is the actual goal.