~~NOTRANS~~

# Greatest Common Divisor by Euclid's Division Algorithm

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.

## Iterative Implementation

#!/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)

## Recursive Implementation

#!/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