Sometimes you need a quick-and-dirty implementation of the greatest common divisor and its extended variant. Actually, because the fractions module comes with a gcd function, the implementation of the extended greatest common divisor algorithm is probably more useful. Both implementations are recursive, but they 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.