Day 13: Extended euclidean algorithm

One of the most fundamentals algorithms in number theory is extended euclidean algorithm. It’s purpose is to solve Diophantine equation

ax + by = GCD(a, b)

Seriously, every programmer must know this one, I don’t even know what else to say.

algorithm

https://github.com/coells/100days

def gcd(x, y):
    u0, v0 = 1, 0
    u1, v1 = 0, 1
    while y:
        q = x // y
        u0, u1 = u1, u0 - q * u1
        v0, v1 = v1, v0 - q * v1
        x, y = y, x % y
    return x, u0, v0

test

> gcd(2*3*7*9*11, 6*12*13)
(18, -9, 40)
> gcd(151, 100)
(1, -49, 74)