Extended Euclidean Algorithm
Find GCD and Bézout coefficients with step-by-step solutions
- Enter two integers a and b to find their greatest common divisor (GCD)
- The algorithm also finds Bézout's coefficients (x, y) such that ax + by = gcd(a,b)
- The table shows each step of the algorithm's execution
- The process continues until the remainder becomes 0
Applications: Cryptography, finding modular inverses, solving linear Diophantine equations
What is the Extended Euclidean Algorithm?
The Extended Euclidean Algorithm extends the standard Euclidean Algorithm to not only find the GCD of two numbers a and b, but also find integers x and y such that ax + by = GCD(a,b). These x and y are called Bezout coefficients after the French mathematician Etienne Bezout.
What is Bezout's Identity?
Bezout's Identity states that for any integers a and b with GCD d, there exist integers x and y such that ax + by = d. The Extended Euclidean Algorithm computes these coefficients. For example, for 240 and 46, GCD = 2, and 240(-9) + 46(47) = 2.
Why is the Extended Euclidean Algorithm important?
It's essential for finding modular multiplicative inverses, which are crucial in RSA encryption and other cryptographic systems. If ax + by = 1, then x is the multiplicative inverse of a modulo b. It's also used for solving linear Diophantine equations.
What are linear Diophantine equations?
Linear Diophantine equations are equations of the form ax + by = c where solutions must be integers. The equation has integer solutions if and only if GCD(a,b) divides c. The Extended Euclidean Algorithm provides the foundation for finding all integer solutions.