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.

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.