javascript-algorithms

javascript-algorithms copied to clipboard

While the Euclidean algorithm calculates only the greatest common divisor (GCD) of two integers a and b, the extended version also finds a way to represent GCD in terms of a and b, i.e. coefficients x and y for which: a * x + b * y = gcd(a, b). This is extremely useful in the application of the chinese remainder theorem and calculating modular inverses.