Enter two integers A and B to find their Greatest Common Divisor (GCD) and Bézout coefficients using the Extended Euclidean Algorithm. The calculator returns the GCD, coefficients x and y satisfying ax + by = gcd(a, b), and a full step-by-step iteration table showing how the algorithm converges.
GCD(A, B)
--
Bézout Coefficient x
--
Bézout Coefficient y
--
Bézout Identity Verified (ax + by)
--
LCM(A, B)
--
The Extended Euclidean Algorithm is a modification of the classical Euclidean GCD algorithm. In addition to computing gcd(a, b), it finds integer coefficients x and y — called Bézout coefficients — such that ax + by = gcd(a, b). This relationship is guaranteed to exist for any two integers by Bézout's identity.
Bézout coefficients x and y are integers satisfying the linear combination ax + by = gcd(a, b). They are especially useful in number theory for solving linear Diophantine equations, computing modular multiplicative inverses, and working with cryptographic algorithms such as RSA.
The algorithm initializes with r₁ = a, r₂ = b, x₁ = 1, x₂ = 0, y₁ = 0, y₂ = 1. At each iteration it computes a quotient q = floor(r_{i-2} / r_{i-1}), then updates r, x, and y using the recurrence: r_i = r_{i-2} − q·r_{i-1}, x_i = x_{i-2} − q·x_{i-1}, y_i = y_{i-2} − q·y_{i-1}. The process stops when the remainder reaches zero, and the last non-zero remainder is the GCD.
The algorithm works with negative integers as well. The GCD is defined as a non-negative value, so gcd(a, b) = gcd(|a|, |b|). The Bézout coefficients x and y will automatically adjust their signs to satisfy ax + by = gcd(a, b) for any combination of positive or negative inputs.
Yes. If gcd(a, n) = 1 (i.e., a and n are coprime), then the Bézout coefficient x found by setting A = a and B = n gives the modular multiplicative inverse of a modulo n. That means a·x ≡ 1 (mod n). This is a key operation in RSA encryption and other cryptographic systems.
The basic Euclidean Algorithm only computes gcd(a, b) by repeatedly applying the division rule. The Extended version does the same but additionally back-substitutes through the steps to express the GCD as a linear combination of a and b, yielding the Bézout coefficients x and y.
No, the Bézout coefficients are not unique. If (x, y) is one solution to ax + by = gcd(a, b), then (x + k·b/gcd, y − k·a/gcd) is also a solution for any integer k. The Extended Euclidean Algorithm returns one specific solution, typically with the smallest absolute values arising naturally from the back-substitution.
If either input is zero, gcd(a, 0) = |a| and gcd(0, b) = |b| by convention. The algorithm handles this as a degenerate case: the non-zero number is the GCD, and the corresponding coefficient is 1 while the other is 0. This calculator will show a result but the step table will be minimal.