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.

And: Wolfram Function Definition -- ExtendedGCD

Return to Number Theory, Algorithms, and Real Functions
Return to Harry's Home Page

---

This page accessed times since March 26, 2005.
Page created by: hjsmithh@sbcglobal.net
Changes last made on Monday, 06-Aug-07 20:47:21 PDT

---