def euclid(a, b):
    if b == 0:
        return a
    else:
        if a > b:
            return euclid(a - b, b)
        else:
            return euclid(a, b - a)