Extended Euclidean Algorithm (Bézout)
Compute the greatest common divisor of two integers a and b together with the Bézout coefficients x, y satisfying a·x + b·y = gcd(a,b) — Bézout's identity. Shows every step of the extended Euclidean algorithm (quotients, remainders, and the running coefficients). When the two inputs are coprime, it also gives the modular inverse of a mod b. All arithmetic uses big integers, so it is exact for any size. Runs locally in your browser.
Input
Result
Extended Euclidean table
The extended Euclidean algorithm runs the ordinary Euclidean algorithm while keeping two extra rows of coefficients s and t (started at 1, 0 and 0, 1), each updated by new = prev − quotient·cur exactly as the remainders are. When the remainder reaches 0, the previous remainder is the gcd and its coefficient rows are the Bézout pair: a·s + b·t = gcd. The gcd is always returned non-negative; for negative inputs the coefficients are adjusted so the identity still holds. When gcd(a,b) = 1, the coefficient x reduced mod |b| is the modular inverse of a (and vice versa). Pairs with the GCD & LCM, Modular Arithmetic, and Chinese Remainder Theorem tools. Everything runs locally — nothing leaves your browser.