chickadee » modular-arithmetic » xgcd

Computes the "extended greatest common divisor" of a and b, ie. it returns the two values x and y that constitute the solution of the equation

 x*a + y*b = gcd(a, b)