gcd(11, 17) == 1
17 = 11(1) + 6 // 1 is floor(17/11), 6 is 17 mod 11
11 = 6(1) + 5
6 = 5(1) + 1 // done
Implementation in python (src)
def gcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = gcd(b % a, a)
return (g, y - (b // a) * x, x)