Extended Euclidean Calculator

Enter two integers into the calculator to determine their greatest common divisor (GCD) and the coefficients of the Extended Euclidean Algorithm.

• Bowmar Macro Calculator
• Suburban Computer Paycheck Calculator
• Daemen GPA Calculator

Extended Euclidean Algorithm Explanation

The Extended Euclidean Algorithm is an extension of the Euclidean Algorithm, which is used to find the greatest common divisor (GCD) of two integers. The Extended Euclidean Algorithm not only computes the GCD of two integers a and b, but also finds the coefficients x and y such that:

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

These coefficients (x and y) are useful in many areas of number theory, including solving Diophantine equations and computing modular inverses.

Understanding the Algorithm

The Euclidean Algorithm for finding the GCD of two integers a and b (with a > b) is based on the principle that the GCD of a and b is the same as the GCD of b and a % b (the remainder of the division of a by b). The process is repeated until