func main()
    while (0 == 0)      # Infinite loop
        println("Input 2 integer numbers (two zeroes for the end):");
        print("m = ");
        m = int(scan());
        print("n = ");
        n = int(scan());
        if (m == 0 && n == 0)
            break;
        endif
        d = gcd(m, n);
        println("gcd(m, n) = ", d);
        println("Extended Euclid algoritm:");
        res = extEucl(m, n);
        println("d = ", res[0], ", u = ", res[1], ", v = ", res[2]);
        println("d == gcd(m, n) == u*m + v*n\n");
    endwhile
endfunc

# Recursive implementation of gcd
func gcd(a, b)
    if (b == 0)
        return a;
    else
        return gcd(b, a%b);
    endif
endfunc

# Extended Euclid Algorithm:
# For integers m, n compute d = gcd(m, n)
#     and u, v such that d = u*m + v*n
func extEucl(m, n)
    a = m; b = n;
    u1 = 1; v1 = 0;
    u2 = 0; v2 = 1;
    while (b != 0)
        # Invariant: a == u1*m + v1*n
        #            b == u2*m + v2*n
        #            gcd(a, b) == gcd(m, n)
        q = a/b; r = a%b;
        a = b; b = r;
        tmp = u1; u1 = u2; u2 = tmp - q*u2;
        tmp = v1; v1 = v2; v2 = tmp - q*v2;
    endwhile
    return [a, u1, v1];
endfunc

main();