# Algorithm Implementation/Mathematics/Extended Euclidean algorithm

Jump to: navigation, search

## Python

Both functions take positive integers a, b as input, and return a triple (g, x, y), such that ax + by = g = gcd(a, b).

### Iterative algorithm

def egcd(a, b):
x,y, u,v = 0,1, 1,0
while a != 0:
q, r = b//a, b%a
m, n = x-u*q, y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
gcd = b
return gcd, x, y

### Recursive algorithm

def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

### Modular inverse

An application of extended GCD algorithm to finding modular inverses:

def modinv(a, m):
gcd, x, y = egcd(a, m)
if gcd != 1:
return None  # modular inverse does not exist
else:
return x % m

## Haskell

### Unextended

euclid :: Integral a => a -> a -> a
euclid 0 b = abs b
euclid a 0 = abs a
euclid a b = euclid b \$ rem a b

### Extended

eGCD :: Integral a => a -> a -> (a,a,a)
eGCD a 0 = (a, 1, 0)
eGCD a b = let (g, x, y) = eGCD b \$ rem a b
in (g, y, x - (a `div` b) * y)