def euclides(a,b):
        return a if b == 0 else euclides(b, a%b)

def euclides_ext(a,b):
    if b == 0:
        return [1,0,a]
    else:
        x,y,d = euclides_ext(b, a%b)
    return [y, x - (a//b)*y, d]

print euclides(112,70)
print euclides_ext(112,70)