Extended Euclidean Algorithm

In [here], the euclidean algorithms i.e. gcd and lcm are presented. Especially the gcd function, which computes the greatest common divisor, is fundamentally important in math and can be implemented by two methods, the iterative one and the recursive one.

The Extended Euclidean Algorithm is the extension of the gcd algorithm, but in addition, computes two integers, x and y, that satisfies the following.

The Python implementation of the Extended Euclidean Algorithm is as follows, where it is recommended that the Iterative approach should be used because of the higher computation efficiency over the recursive one.

#!/usr/bin/env python
# https://helloacm.com

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

def extended_gcd2(a, b):
    if b == 0:
        return (1, 0)
    else:
        q, r = a / b, a % b
        s, t = extended_gcd2(b, r)
        return (t, s - q * t)
    
if __name__ == "__main__":
    print extended_gcd1(27, 21)
    print extended_gcd2(27, 21)

It is worth to mention that the pair (x, y) is not unique, because if you increase x by b and reduce y by a, the sum remain unchanged.

By a little adjustment, the extended gcd function can return the gcd value as well, together with x and y.

# acm.steakovercooked.com

# return a tuple which is (gcd, x, y)
def extended_gcd3(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        q, r = a / b, a % b
        u, s, t = extended_gcd3(b, r)
        return (u, t, s - q * t)

–EOF (The Ultimate Computing & Technology Blog) —