def gcd(a, b):
    big = max(a, b)
    small = min(a, b)
    if big % small == 0:
        return small
    return gcd(small, big % small)