Sometimes you need quick and dirty implementation of greatest common divisor and its extended variant. Actually, because the
fractions module comes
gcd function, probably the implementation of the exteded greatest common divisor algorithm is more useful. Both implementations are recursive, but work nonetheless even for comparatively large integers.
# simply returns the gcd gcd = lambda a,b: gcd(b, a % b) if b else a # egcd(a,b) returns (d,x,y) where d == a*x + b*y egcd = lambda a,b: (lambda d,x,y: (d, y, x - (a // b) * y))(*egcd(b, a % b)) if b else (a, 1, 0)
The code above is Python 2 and 3 compatible.