simple python implementation of the extended euclidean algorithm

euclides.py

def euclides(a, b):
    S = []
    while a % b != 0:
        S.append(a // b)
        a, b = b, a % b
    x1, x2 = 1, -S.pop()
    while len(S):
        q = S.pop()
        x1, x2 = x2, x1 - x2*q
    return (b, x1, x2)