The extended Euclidean algorithm (xgcd) takes two positive numbers M,N and successively divides one number into another and computes directly the integer quotient and remainder at each stage. This algorithm produces a strictly decreasing sequence of remainders that terminates at zero, where the last nonzero remainder in the sequence is the greatest common denominator (gcd) g.
The Sage command g,x,y = gcd(M,N) returns the triple g,x,y for which g = x*M + y*N.