```
// -----------------------------------------------------------------------------
// The extended Euclidean algorithm computes for given integers a,b numbers g,
// u and v such that g = gcd(a,b) = u*a + v*b holds. It also computes numbers
// s and t such that 0 = s*a + t*b holds.
// -----------------------------------------------------------------------------

function ExtEuclid(int a,b):int {
int q;
int m,n,u,v,s,t;
int m1,n1,u1,v1;

m = a;
n = b;
u = +1;
v = +0;
s = +0;
t = +1;
assert(m == (u*a + v*b));
assert(n == (s*a + t*b));

// The loop maintains the following invariants:
//    (1) m == u*a + v*b
//    (2) n == s*a + t*b
//    (3) gcd(m,n) = gcd(a,b)
// Note that (3) is invariant since gcd(m,n) = gcd(n,m%n), and the other
// invariants are immediately seen by expanding the assignments.

while(n!= +0) {
q = m / n;
m1 = n;
n1 = m - q * n;
u1 = s;
v1 = t;
s = u - q * s;
t = v - q * t;
m = m1;
n = n1;
u = u1;
v = v1;
assert(m == (u*a + v*b));
assert(n == (s*a + t*b));
}
// since n=0 holds, we conclude the following from the invariants
//    (1) m == u*a + v*b
//    (2) 0 == s*a + t*b
//    (3) gcd(m,0) = m = gcd(a,b)
return m;
}