# Extended Euclidean algorithm

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

## Code

# 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

Function parameters ${\displaystyle X,Y}$ are by reference and are used to return values, ${\displaystyle Xprime,Yprime,res}$ are helper variables. All division is integer ${\displaystyle {a \over b}=floor({a \over b})}$. The goal of algorithm, is to find ${\displaystyle X}$ and ${\displaystyle Y}$, such that ${\displaystyle aX+bY=\gcd(a,b)}$. It works basicaly in the same way as Euclidean algorithm

• When b = 0
 Simply ${\displaystyle aX+bY=\gcd(a,b)}$, holds when ${\displaystyle X=1,Y=0}$, since ${\displaystyle gcd(a,0)=a}$

• Otherwise recursion is used, and ${\displaystyle Xprime}$ and ${\displaystyle Yprime}$, are comuted such that,

${\displaystyle bX^{\prime }+(a\mod b)Y^{\prime }=gcd(a,b)}$. From this valus, we can can compute values ${\displaystyle X}$ and ${\displaystyle Y}$, such that ${\displaystyle aX+bY=gcd(a,b)}$. Imagine if we put,

${\displaystyle X=Y^{\prime },Y=X^{\prime }}$. We would get such equation ${\displaystyle aX+bY=aY^{\prime }+bX^{\prime }=(a{\bmod {b}}+{a \over b}bY^{\prime }+bX^{\prime }=bX^{\prime }+(a{\bmod {b}})Y^{\prime }+({a \over b}bY^{\prime }=gcd(a,b)+{a \over b}Y^{\prime }b}$, important is that ${\displaystyle aY^{\prime }+bX^{\prime }=gcd(a,b)+{a \over b}Y^{\prime }b}$, where we can move ${\displaystyle {a \over b}Y^{\prime }b}$ to the left side, and then take out ${\displaystyle b}$, to get ${\displaystyle aY^{\prime }+b(X^{\prime }-{a \over b}Y^{\prime })=gcd(a,b)}$. So if we put ${\displaystyle X=Y^{\prime }}$ and ${\displaystyle Y=X^{\prime }-{a \over b}Y^{\prime }}$, ${\displaystyle aX+bY=gcd(a,b)}$ will hold.