Extended Euclidean Algorithm Calculator – GCD and Bezout Coefficients
The Extended Euclidean Algorithm goes one step further than a plain GCD calculation. Given two integers a and b, it finds not only gcd(a, b) but also a pair of integers x and y — the Bezout coefficients — such that a×x + b×y = gcd(a, b). This identity, known as Bezout's identity, underlies modular inverses, RSA key generation, and the solution of linear Diophantine equations. This calculator shows every step of the process, from the initial division chain through the back-substitution that recovers x and y.
The Forward Pass: Euclidean Division
The algorithm starts exactly like the ordinary Euclidean algorithm. It divides a by b, records the quotient and remainder, then repeats the process on b and the remainder — dividend = quotient × divisor + remainder — until a remainder of zero is reached. The last nonzero remainder is the GCD. For a = 99, b = 78, the chain runs 99 = 1×78 + 21, 78 = 3×21 + 15, 21 = 1×15 + 6, 15 = 2×6 + 3, and finally 6 = 2×3 + 0, leaving gcd(99, 78) = 3.
The Backward Pass: Back-Substitution
Once the GCD is found, the calculator walks the same division chain in reverse. Starting from the equation that produced the GCD, it substitutes each prior equation upward, one remainder at a time, replacing two remainders with a single running combination of the numbers immediately above them. After working all the way back to the top, the combination is expressed purely in terms of the original a and b, yielding the Bezout coefficients directly. For the example above, this process recovers x = -11 and y = 14, since 99×(-11) + 78×14 = -1089 + 1092 = 3.
(x, y) satisfies a×x + b×y = gcd(a, b), then (x + (b/g)×t, y − (a/g)×t) is also a valid pair for any integer t, where g = gcd(a, b). The calculator returns the specific pair produced by standard back-substitution, the same result most textbooks and reference implementations report.Solving Linear Diophantine Equations
A linear Diophantine equation asks for integer solutions to ax + by = c. A solution exists exactly when gcd(a, b) divides c evenly. When it does, scaling the Bezout coefficients by c / gcd(a, b) produces one particular solution: for 6x + 9y = 3, gcd(6, 9) = 3 divides 3, so a solution exists. When it does not — as with 4x + 6y = 5, where gcd(4, 6) = 2 does not divide 5 — the calculator reports that no integer solution exists rather than an approximate answer.
The General Solution Family
A single particular solution is only one member of an infinite family. Every integer solution to ax + by = c can be written as x = x₀ + (b/g)·t and y = y₀ − (a/g)·t for any integer t, where (x₀, y₀) is the particular solution and g = gcd(a, b). Enabling the general solution toggle displays this parametric formula alongside the particular solution, so you can generate as many valid pairs as you need.
Why This Matters: RSA and Modular Inverses
The Extended Euclidean Algorithm is the standard way to compute a modular multiplicative inverse: when gcd(a, m) = 1, the Bezout coefficient x in a×x + m×y = 1 satisfies a×x ≡ 1 (mod m), making x the inverse of a modulo m. This is a core step in RSA key generation, where the private exponent is the modular inverse of the public exponent, and it appears throughout number theory whenever a linear combination of two integers needs to be expressed explicitly.
Precision, Signs, and Limits
Every value is computed using arbitrary-precision BigInt arithmetic, so inputs with up to 300 digits are supported without the rounding errors that would eventually appear with ordinary floating-point numbers. Negative integers are handled automatically: the algorithm works internally with absolute values and adjusts the sign of the resulting coefficients so the identity still holds for your original, signed inputs. The only invalid input is a = 0 and b = 0 together, since their greatest common divisor is undefined.