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.

One practical detail that trips people up: the x the algorithm hands back is often negative, and a modular inverse is normally quoted as a residue between 0 and m-1. Add m until it lands in range. For a = 3 and m = 7 the algorithm gives x = -2, and -2 + 7 = 5, so the inverse is 5. Both are correct, since -2 and 5 are the same number modulo 7, but 5 is the one a textbook prints. This calculator does the shift for you and shows the raw coefficient alongside it.

The classic RSA worked example runs through here directly. With p = 61 and q = 53 you get phi(n) = 60 * 52 = 3120, and the usual public exponent e = 17. Enter 17 and 3120: the gcd is 1, so 17 is a legal choice, and the inverse comes out 2753. That is the private exponent d in every RSA textbook. Check it: 17 * 2753 = 46,801, and 46,801 = 15 * 3120 + 1.

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.