def euclide_gcd_algo(a, b):
    """Calculate (r, u, v) so that u * a + v * b = r = GCD(a, b)"""
    (r, u, v, r2, u2, v2) = (a, 1, 0, b, 0, 1)
    while r2 > 0:
        q = r // r2
        (r, u, v, r2, u2, v2) = (r2, u2, v2, r - q * r2, u - q * u2, v - q * v2)
    return r, u, v