Encyclopedia > Extended Euclidean algorithm

  Article Content

Extended Euclidean algorithm

The Extended Euclidean algorithm is a version of the Euclidean Algorithm; its input are two integers a and b and the algorithm computes their greatest common divisor (GCD) as well as integers x and y such that ax + by = gcd(a,b). This works because the steps of Euclid's algorithm always deal with sums of multiples of a and b.

The equation ax + by = gcd(a,b) is particularly useful when a and b are relatively prime: x is then the multiplicative inverse of a modulo b.

Consider as an example the computation of gcd(120,23) with Euclid's algorithm:


120 / 23 = 5 r 5
23  / 5  = 4 r 3
5   / 3  = 1 r 2
3   / 2  = 1 r 1
2   / 1  = 2 r 0

In this case, the remainder in the second-to-last line indicates that the gcd is 1; that is, 120 and 23 are coprime. Now do a little algebra on each of the above lines:

120 / 23 = 5 r 5   => 5 = 120 - 5*23
23  / 5  = 4 r 3   => 3 = 23  - 4*5
5   / 3  = 1 r 2   => 2 = 5   - 1*3
3   / 2  = 1 r 1   => 1 = 3   - 1*2
2   / 1  = 2 r 0   => 0 = 2   - 2*1

Now observe that the first line contains multiples of 120 and 23. Also, the rightmost values are in each case the remainders listed on the previous line, and the left side of the differences are the residues from 2 lines up. We can thus progressively calculate each successive remainder as sums of products of our two original values.

Here we rewrite the second equations in the above table:

  5 = 120 - 5*23  = 1*120            - 5*23
  3 = 23  - 4*5   = 1*23             - 4*(1*120  - 5*23)   =  -4*120 + 21*23
  2 = 5   - 1*3   = (1*120 - 5*23)   - 1*(-4*120 + 21*23)  =   5*120 - 26*23
  1 = 3   - 1*2   = (-4*120 + 21*23) - 1*(5*120  - 26*23)  =  -9*120 + 47*23

Notice that the last line says that 1 = -9*120 + 47*23, which is what we wanted: x = -9 and y = 47.

This means that -9 is the multiplicative inverse of 120 modulo 23, because 1 = -9 * 120 (mod 23).

Here is a JavaScript implementation of the Extended Euclidean algorithm which should work in most browsers:

// This program works only for non-negative inputs.
// Get data from user and convert strings to integers.
var a = parseInt(prompt("Enter non-negative value for a",0))
var b = parseInt(prompt("Enter non-negative value for b",0))

// Save original values.
a0 = a;
b0 = b;

// Initializations. We maintain the invariant p*a0 + q*b0 = a and r*a0 + s*b0 = b.
p = 1; q = 0;
r = 0; s = 1;

// The algorithm:
while (b != 0) { 
  c = a % b;
  quot = Math.floor(a/b);  //Javascript doesn't have an integer division operator
  a = b;
  b = c;
  new_r = p - quot * r; new_s = q - quot * s;
  p = r; q = s;
  r = new_r; s = new_s;
}

// Show result.

alert("gcd(" + a0 + "," + b0 + ")=" p + "*" + a0 + 
      "+(" + q + ")*" + b0 + "=" + a)


External links:



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Holtsville, New York

...     Contents Holtsville, New York Holtsville is a town located in Suffolk County, New York. As of the 2000 census, the town had a ...

 
 
 
This page was created in 36.2 ms