# Extended Euclidean algorithm

Jump to navigation
Jump to search

This is a stub or unfinished. Contribute by editing me. |

## Code[edit]

```
# Iterative algorithm
def iterative_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
return b, x, y
# Recursive algorithm
def recursive_egcd(a, b):
"""Returns a triple (g, x, y), such that ax + by = g = gcd(a,b).
Assumes a, b >= 0, and that at least one of them is > 0.
Bounds on output values: |x|, |y| <= max(a, b)."""
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
```

## Explanation[edit]

Function parameters are by reference and are used to return values, are helper variables. All division is integer . The goal of algorithm, is to find and , such that . It works basicaly in the same way as Euclidean algorithm

- When b = 0

Simply , holds when , since

- Otherwise recursion is used, and and , are comuted such that,

. From this valus, we can can compute values and , such that . Imagine if we put,

. We would get such equation , important is that , where we can move to the left side, and then take out , to get . So if we put and , will hold.