One of the most popular definition in mathematics is the Greatest Common Divisor or GCD. If i am not wrong, I studied about GCD in primary school or secondary school after I learned division. At that time, I don't know why I need to use GCD other than for calculating Fraction. Actually, GCD is used so often in high-level mathematics and computer sciences. Since it is very popular, there are many approaches for finding GCD of given numbers.

The most well-known algorithm for finding GCD is Euclidean Algorithm which could be implemented in several ways.

Recursion

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a % b)

Iteration

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

Pythonic version:

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

Another useful algorithm is called Extended Euclidean Algorithm. In addition to the GCD, it also gives x and y which satisfy below identity.

ax + by = gcd(a,b)

This algorithm is widely used in Modular Exponentiation.

def extended_gcd(a,b):
    x,y = 0,1
    lastx,lasty = 1,0
    while b != 0:
        temp = b
        quotient = a/b
        b = a%b
        a = temp
 
        temp = x
        x = lastx-quotient*x
        lastx = temp
 
        temp = y
        y = lasty-quotient*y
        lasty = temp
 
    return a,lastx,lasty

Pythonic version:

def extended_gcd(a,b):
    x,y = 0,1
    lastx,lasty = 1,0
    while b != 0:
        a,(quotient,b) = b,divmod(a,b)
        x,lastx = lastx-quotient*x,x
        y,lasty = lasty-quotient*y,y
    return a,lastx,lasty

I will discuss about how to use GCD and above algorithms in more detail later.

Note that Pythonic versions are taken from below excellent comment by Paddy.

Tags: greatest common divisor, euclidean, python, mathematics