# gcditer
# Fig. 6.3 

def gcd(a,b):
  while b > 0:
    a, b = b, a%b
  return a