# Extended Greatest Common Divisor

The extended form of Euclid's algorithm computes g = GCD(a, b) of the two integers a and b and also determines u and v such that g = GCD(a, b) = a*u + b*v.

```
First set a = |a| and b = |b|, then

(u, v, g) = GCDe(a, b) // Extended Euclid's algorithm
//non-recursive version, from Knuth ACP vol. 2, pg. 302 section 5.5.2 Algorithm X
// g will be >= 0 but u or v may be <= 0.
{
u  = 1;  v  = 0;  g  = a;
u1 = 0;  v1 = 1;  g1 = b;
while (g1 != 0)
{
q = g/g1; // Integer divide
t1 = u - q*u1;   t2 = v - q*v1;   t3 = g - q*g1;
u  = u1;         v  = v1;         g  = g1;
u1 = t1;         v1 = t2;         g1 = t3;
}
}

For example, let a = 54321 and b = 12345.
GCDe(54321, 12345)

q     u     v    g      u1      v1    g1
-     1     0  54321     0       1  12345
4     0     1  12345     1      -4   4941
2     1    -4   4941    -2       9   2463
2    -2     9   2463     5     -22     15
164     5   -22     15  -822    3617      3
5  -822  3617      3  4115  -18107      0

GCD(54321, 12345) = 3 = -822*54321 + 3617*12345.
```
See: Extended Greatest Common Divisor -- From MathWorld
And: Wolfram Function Definition -- ExtendedGCD