def gcd(a, b):
    """
    Greatest common divisor (greatest common factor)

    Notes
    ---------

    Euclidean algorithm:

    a > b > r_1 > r_2 > ... > r_n
    a = b*q + r
    b = r_1*q_1 + r_2
    ...
    r_n-1 = r_n*q_n

    gcd(a,b) = gcd(b,r)
    gcd(a,0) = a

    """

    while b != 0:
        a, b = b, a % b
    return a