Bezout's identity and the extended Euclidean algorithm
For any pair of integers a and b there are always integers x and y that satisfy ax+by=gcd(a,b). That statement is Bezout's identity, and the pair x, y is called the Bezout coefficients. The extended Euclidean algorithm is how you actually find them. The ordinary algorithm divides repeatedly until the remainder is zero and reports only the greatest common divisor; the extended version carries two coefficient rows along with each division, so x and y fall out at the end.
This calculator runs the algorithm on absolute values and then folds the input signs back into the coefficients, so negative inputs give correct results. Once it finishes, it substitutes the coefficients back into the original expression and prints that line, which lets you confirm at a glance that the left side really equals the greatest common divisor.
There is never just one solution. Given one pair, every integer k produces another valid pair x+k(b/g) and y−k(a/g), so the general form is listed too. When the greatest common divisor is 1 an extra coprime row appears, and in that case x is the modular inverse of a modulo b, which is exactly how RSA style key setup uses this algorithm. The table below lists each division step in order. To keep the integer arithmetic exact, inputs are limited to one million in absolute value and decimals are not supported.
Frequently Asked Questions
For any two integers a and b there are always integers x and y with ax+by=gcd(a,b). Those two integers are called the Bezout coefficients.
No, there are infinitely many. Given one pair x and y, every integer k gives another solution x+k(b/g) and y−k(a/g), so the general form is shown with the result.
Yes. The algorithm runs on absolute values and the input signs are folded back into the coefficients. Only a and b both being zero is rejected, because the greatest common divisor is undefined there.