def euclid(a, b):
    """
    Applies the Euclidean algorithm to find gcd(a, b)
    PARAMS:
        a (int)
        b (int)
    RETURNS:
        int: The greatest common demoninator
    """
    if a < b:
        a, b = b, a

    if a % b == 0:
        return b

    q = a % b

    return euclid(b, q)