# Extended Euclidean algorithm

static void Main(string[] args)
{
//Solving ax + by = gcd(a, b);
int[] result = SolveByIterativeExtendedEuclideanAlgorithm(21, 9);
Console.WriteLine("Iterative result: x:{0}, y:{1}", result[0], result[1]);
result = SolveByRecursiveExtendedEuclideanAlgorithm(21, 9);
Console.WriteLine("Recursive result: x:{0}, y:{1}", result[0], result[1]);
result = SolveByIterativeExtendedEuclideanAlgorithm2(21, 9);
Console.WriteLine("Recursive result: x:{0}, y:{1}", result[0], result[1]);
}

/// <summary>
/// Extended Euclidean algorithm
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <seealso cref="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm"/>
/// <returns></returns>
private static int[] SolveByIterativeExtendedEuclideanAlgorithm(int a, int b)
{
//Initialize x0, x1 as 1, 0, and y0, y1 as 0,1 respectively.
int lastX = 1, x = 0;
int lastY = 0, y = 1;
int temp = 0;
int quotient = 0;
while(b != 0)
{
temp = b;
quotient = a / b;
b = a % b;
a = temp;
//Compute xi+1= xi-1- qixi
temp = x;
x = lastX – quotient * x;
lastX = temp;
//Compute yi+1= yi-1- qiyi
temp = y;
y = lastY – quotient * y;
lastY = temp;
}
//The answers are the second-to-last of xn and yn.
return new int[] { lastX, lastY };
}

/// <summary>
/// Extended Euclidean algorithm
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <seealso cref="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm"/>
/// <returns></returns>
private static int[] SolveByRecursiveExtendedEuclideanAlgorithm(int a, int b)
{
// If a is divisible by b, the algorithm ends and return the trivial solution x = 0, y = 1.
if ((a % b) == 0)
return new int[] { 0, 1 };
//Otherwise, repeat the algorithm with b and a modulus b, storing the solution as x’ and y’.
int[] result = SolveByRecursiveExtendedEuclideanAlgorithm(b, a % b);
//Then, the solution to the current equation is x = y’, and y = x’ minus y’ times quotient of a divided by b
return new int[] {result[1], result[0] – a / b * result[1] };
}

private static int[] SolveByIterativeExtendedEuclideanAlgorithm2(int a, int b)
{
int m = a;
int n = b;
int p = 1;
int q = 0;
int r = 0;
int s = 1;
while (! ((m == 0) || (n == 0)) )
{
if (m >= n)
{
m = m – n;
p = p – r;
q = q – s;
}
else
{
n = n – m;
r = r – p;
s = s – q;
}
}
if (m == 0)
{
return new int[] { r, s};
}
else
{
return new int[] { p, q};
}
}