def euclidean_algo(a: int, b: int) -> int:
    while b: a, b = b, a % b
    return a

'''
Calculates coefficients x and y of Bezout's identity: ax + by = gcd(a,b)  
NOTE: Based on the Extended Euclidean Algorithm's Wikipedia page
'''
def extended_euclid_algo(a: int, b: int) -> tuple[int, int]:
    (old_r, r) = (a, b)
    (old_s, s) = (1, 0)
    (old_t, t) = (0, 1)
    while r != 0:
        q = old_r // r
        (old_r, r) = (r, old_r - q*r)
        (old_s, s) = (s, old_s - q*s)
        (old_t, t) = (t, old_t - q*t)
    # Bezout cofficients:     (old_s, old_t)
    # Greatest Common Divisor: old_r
    # Quotients by the gcd:   (t, s)
    return (t, s)