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.