gcd(a, b):  

    while 0 < b:
        r ← a % b   # a を b で割った余り
        a ← b
        b ← r

    return a