def ext_euclid_alg (m, n):
    """ Extended Euclidean algorithm for gcd.

    Finds the greatest common divisor of
    two integers a and bm and solves for integer
    x, y such that ax + by = 1.  From Knuth, TAOCP
    vol. I, p. 14.
    Variables --
        q, r -- quotient and remainder
        a, b -- am + bn = gcd
        apme, bpme -- a prime and b prime
        t -- temporary
    """

    m, n = abs(m), abs(n)
    q, r = m // n, m % n
    apme = b = 1
    a = bpme = 0

    while  r != 0:
        m, n = n, r 
        t = apme
        apme = a
        a = t - q * a
        t = bpme
        bpme = b
        b = t - q * b
        """ reset q and r """
        q, r = m // n, m % n

    return (n, a, b)