Extended Euclidean Algorithm.sagews

def extEuclAlg(a, b):
    u = 1
    g = a
    x = 0
    y = b
    while True:
        if y == 0:
            v = (g- a*u)/b
            return [g, u, v]
        q = floor(g/y)
        t = int(mod(g,y))
        s = u - q*x
        u = x
        g = y
        x = s
        y = t

        
def _extEuclAlg(a, b):
    u = 1
    g = a
    x = 0
    y = b
    while True:
        if y == 0:
            v = (g- a*u)/b
            return [g, u+b/g, v-a/g]
        q = floor(g/y)
        t = int(mod(g,y))
        s = u - q*x
        u = x
        g = y
        x = s
        y = t
        
var = extEuclAlg(8675309, 3892394)
print var

[1, -843845, 1880749]

var = _extEuclAlg(8675309, 3892394)
print var

[1, 3048549, -6794560]

factor(85)
factor(285)
factor(697)

5 * 17 3 * 5 * 19 17 * 41