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

• When b = 0
 Simply $aX+bY=\gcd(a,b)$ , holds when $X=1,Y=0$ , since $gcd(a,0)=a$ • Otherwise recursion is used, and $Xprime$ and $Yprime$ , are comuted such that,

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

$X=Y^{\prime },Y=X^{\prime }$ . We would get such equation $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 $aY^{\prime }+bX^{\prime }=gcd(a,b)+{a \over b}Y^{\prime }b$ , where we can move ${a \over b}Y^{\prime }b$ to the left side, and then take out $b$ , to get $aY^{\prime }+b(X^{\prime }-{a \over b}Y^{\prime })=gcd(a,b)$ . So if we put $X=Y^{\prime }$ and $Y=X^{\prime }-{a \over b}Y^{\prime }$ , $aX+bY=gcd(a,b)$ will hold.