extended euclidean algorithm

1def extendEuclidean(a, b, s1=1, s2=0, t1=0, t2=1):
2    
3    if b:
4        r=a%b
5        return extendEuclidean(b, r, s2, s1-s2*(a//b), t2, t1-t2*(a//b))
6    
7    return a, s1, t1

1int gcd(int a, int b, int& x, int& y) {
2    if (b == 0) {
3        x = 1;
4        y = 0;
5        return a;
6    }
7    int x1, y1;
8    int d = gcd(b, a % b, x1, y1);
9    x = y1;
10    y = x1 - y1 * (a / b);
11    return d;
12}
13