xgcd() -- Multiple-Precision Mathematics (libmp)

Extended greatest-common-divisor function
#include <mprec.h>
void xgcd(a, b, r, s, g)
mint *a, *b, *r, *s, *g;

xgcd() is an extended version of the greatest-common-division function.  It
sets  the multiple-precision  integer  (or mint)  pointed  to by  g to  the
greatest common divisor of the mint  pointed to by a and that pointed to by
b. It also  sets the mints pointed to by  r and s so the following relation
holds:

    g = a × r + b × s

r, s, and g must all be distinct.

See Also

libmp

© 2012 by Stephen A. Ness