Extended Euclidean Algorithm Calculator

The Extended Euclidean Algorithm finds not only the greatest common divisor of two integers a and b, but also integers x and y (called Bezout coefficients) such that ax + by = gcd(a, b). This is Bezout’s identity, and it holds for any pair of integers.

The standard Euclidean algorithm divides repeatedly: a = q*b + r, then replaces (a, b) with (b, r), and repeats until the remainder is zero. The last nonzero remainder is the GCD.

The extended version tracks two extra sequences alongside the quotients. At each step, it records how the current remainder can be expressed as a linear combination of the original a and b. When the algorithm terminates, those coefficients are the Bezout coefficients.

For example, gcd(35, 15): 35 = 215 + 5, then 15 = 35 + 0. So gcd = 5. Working backwards: 5 = 35 - 215, giving x = 1, y = -2. Check: 351 + 15*(-2) = 35 - 30 = 5. Correct.

Bezout coefficients are not unique. Adding b/gcd to x and subtracting a/gcd from y gives another valid pair. The algorithm returns one particular solution.

The main application of the Extended Euclidean Algorithm is computing modular inverses. If gcd(a, m) = 1, then the x in ax + my = 1 is the modular inverse of a modulo m. This is used constantly in RSA encryption, the Chinese Remainder Theorem, and elliptic curve cryptography.

For two integers with gcd = 1 (coprime integers), Bezout’s identity guarantees that the linear combination ax + by can produce 1. For integers with gcd = d > 1, the combination can produce d but not any smaller positive integer.