##### $\mathfrak{Mini}$ $\mathbb{Wiki}$

• No tags, yet

1. June 2020

# Greatest Common Divisor by Euclid's Division Algorithm

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