$\mathfrak{Mini}$ $\mathbb{Wiki}$
Please remove syntax.php from lib/plugins/nodisp or remove the plugin and reinstall

1. June 2020 mozgan   

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

This website uses cookies. By using the website, you agree with storing cookies on your computer. Also you acknowledge that you have read and understand our Privacy Policy. If you do not agree leave the website.More information about cookies