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.
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.