Extended Euclidean Algorithm Calculator

It finds the greatest common divisor of two integers a and b, plus two integers x and y, called Bezout coefficients, that satisfy ax + by = gcd(a, b). The standard Euclidean algorithm gives you only the gcd. The extended version also tracks how each remainder is built from a and b, so when it reaches the gcd it can express that gcd as a linear combination of the two inputs.

Bezout coefficients are the integers x and y in the identity ax + by = gcd(a, b). They prove that the gcd can be written as a whole-number combination of a and b. They are the key step for computing modular inverses, solving linear Diophantine equations like ax + by = c, and setting up the private key in RSA encryption.

Each row holds a remainder r and two coefficients s and t with the property that s times a plus t times b equals r. The first two rows seed the process with (a, 1, 0) and (b, 0, 1). Each later row subtracts a quotient multiple of the row above it. The last row with a non-zero remainder holds the gcd in the r column, and its s and t are the coefficients x and y.

No. For any solution (x, y) you can produce infinitely many others by adding b/gcd to x and subtracting a/gcd from y, which leaves ax + by unchanged. The extended Euclidean algorithm returns one specific pair, the one produced by the back-substitution of the standard remainder sequence. This calculator reports that canonical pair and the verification value so you can confirm it.

Yes, with one exception. If exactly one value is zero, the gcd is the absolute value of the other and the calculator still returns valid coefficients. Negative inputs work too, and the gcd is always reported as non-negative by convention. The only case that is rejected is gcd(0, 0), which is mathematically undefined because every integer divides zero.