Euclid's algorithm finds the greatest common divisor of two nonnegative integers a, b (not both zeros). I have implemented it in JavaScript as follows.


 function gcd(a,b)
 { 
 if (b == 0)
   {return a}
 else
   {return gcd(b, a % b)}
 }

Let's try it.

a = b = gcd(a,b) =


Euclid's extended algorithm finds the greatest common divisor of a, b as well as two integers x, y such that:

ax + by = gcd(a,b).

I have implemented it in JavaScript as follows.


 function xgcd(a,b)
 { 
 if (b == 0)
   {return [1, 0, a]}
 else
   {
    temp = xgcd(b, a % b)
    x = temp[0]
    y = temp[1]
    d = temp[2]
    return [y, x-y*Math.floor(a/b), d]
   }
 }

Let's try it.

a = b = x = y = gcd(a,b) =


Go to Gilles Cazelais Home Page