def euclid(a:int, b:int, Verbose=False):  
    
    """Return the Greatest Common Divisor (GCD) of number a and b."""
    
    # The GCD of two relative integers is equal to the GCD of their absolute values.
    a, b=abs(a), abs(b) 

    # The largest of the two numbers is replaced by the remainder of the Euclidean division of the larger 
    # number by the smaller one. 
    if (b==0) :
        return a
    elif (b>a) :
        return euclid(b, a, Verbose)
    else:
        r=a%b

        if Verbose:
            q=a//b
            print(f"{a} = {b}*{q} + {r}")
    
        return euclid(b, r, Verbose)