For theoretical background see this page.

Let $m, n \in \mathbb{Z}$, then the greatest common divisor $gcd(a, b)$ can be computed with following algorithms.

#!/usr/bin/python
 
def Euclidian(m, n):
    while 1:
        q = m // n
        r = m - n * q
 
        print(str(m) + " = " + str(q) + " x " + str(n) + " + " + str(r))
        assert(r < n)
 
        if r == 0:
            return n
 
        (m, n) = (n, r)

#!/usr/bin/python
 
def Euclidian(m, n):
    q = m // n
    r = m % n # m - n * q
 
    print(str(m) + " = " + str(q) + " x " + str(n) + " + " + str(r))
    assert(r < n)
 
    if r == 0:
        return n
    else:
        return Euclidian(n, r)

Example: Let $m = 2863$ and $n = 1057$.

m = 2863
n = 1057
print("gcd(" + str(m) + ", " + str(n) + ") = " + str(Euclidian(m, n)))

2863 = 2 x 1057 + 749 $\\$ 1057 = 1 x 749 + 308 $\\$ 749 = 2 x 308 + 133 $\\$ 308 = 2 x 133 + 42 $\\$ 133 = 3 x 42 + 7 $\\$ 42 = 6 x 7 + 0 $\\$ gcd(2863, 1057) = 7