Extended Euclidean Algorithm Calculator

The Extended Euclidean Algorithm Calculator computes the Greatest Common Divisor (GCD) of two integers and finds the Bézout coefficients — the integers s and t satisfying gcd(a, b) = s·a + t·b. Beyond computing GCD, this tool provides a fully animated step-by-step division table, back-substitution, and modular inverse computation, making it ideal for number theory courses, cryptography study, and competitive programming.

What is the Extended Euclidean Algorithm?

The Extended Euclidean Algorithm (EEA) is an extension of Euclid's classical GCD algorithm. While the basic algorithm finds gcd(a, b) by successive division, the extended version simultaneously tracks two integer sequences that record how each remainder can be expressed as a linear combination of the original inputs.

How the Algorithm Works

The EEA maintains three pairs of values — (r, s, t) — through each division step:

1. Initialize: r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
2. Each step: compute quotient q = ⌊rₙ₋₁ / rₙ⌋, then update rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ
3. Stop when remainder = 0; the previous remainder is gcd(a, b)
4. The corresponding s and t values are the Bézout coefficients

Step-by-Step Example: gcd(252, 105)

Result: gcd(252, 105) = 21, with Bézout identity: 21 = (−2) × 252 + 5 × 105 (s = −2, t = 5), found by back-substitution: 21 = 105 − 2 × 42 = 105 − 2 × (252 − 2 × 105). Try it with your own numbers in the calculator above.

Applications of the Extended Euclidean Algorithm

1. Modular Inverse (Cryptography)

The most important application is computing modular inverses. If gcd(a, m) = 1, then the Bézout coefficient s satisfies:

Modular inverses are essential in RSA encryption (computing private key exponent d), Diffie-Hellman key exchange, and elliptic curve cryptography.

2. Solving Linear Diophantine Equations

The equation ax + by = c has integer solutions if and only if gcd(a, b) divides c. If so, a particular solution is x₀ = s·(c/d), y₀ = t·(c/d) where d = gcd(a, b) and s, t are the Bézout coefficients.

3. Chinese Remainder Theorem

The EEA is used in the constructive proof and computation of the Chinese Remainder Theorem — finding x such that x ≡ a₁ (mod m₁) and x ≡ a₂ (mod m₂) — by computing modular inverses of the moduli.

4. Fraction Reduction and LCD

gcd(a, b) = 1 confirms that a/b is already in lowest terms. The LCM is lcm(a, b) = |a·b| / gcd(a, b).

Bézout Coefficients Are Not Unique

The Bézout coefficients s and t are not unique. If (s, t) is one solution, then (s + k·(b/d), t − k·(a/d)) is also a solution for any integer k, where d = gcd(a, b). The EEA returns the solution where |s| ≤ |b/d| and |t| ≤ |a/d|.

Time Complexity

The Extended Euclidean Algorithm runs in O(log min(a, b)) iterations — the same as the basic Euclidean algorithm. By Lamé's theorem, the number of steps never exceeds 5 times the number of decimal digits of the smaller input. This makes it extremely efficient even for large integers used in cryptographic applications.

Frequently Asked Questions

What is the Extended Euclidean Algorithm?

The Extended Euclidean Algorithm extends Euclid's GCD algorithm to also compute Bézout coefficients s and t satisfying gcd(a, b) = s·a + t·b. It tracks how each remainder can be expressed as a linear combination of a and b throughout the division process.

What are Bézout coefficients?

Bézout coefficients are integers s and t guaranteed to exist by Bézout's identity (a theorem in number theory). They satisfy gcd(a, b) = s·a + t·b and are computed efficiently by the Extended Euclidean Algorithm. They are used in modular inverse computation, solving Diophantine equations, and the Chinese Remainder Theorem.

How do I find the modular inverse using the Extended Euclidean Algorithm?

If gcd(a, b) = 1 (a and b are coprime), the Bézout coefficient s satisfies s·a ≡ 1 (mod b). The modular inverse of a mod b is s mod b (adjusted to be positive). This calculator displays this directly in the results.

When does the modular inverse not exist?

The modular inverse of a modulo m exists if and only if gcd(a, m) = 1. If gcd(a, m) > 1, no integer x satisfies a·x ≡ 1 (mod m).

What is the time complexity of the Extended Euclidean Algorithm?

O(log min(a, b)) divisions, same as the basic Euclidean algorithm. By Lamé's theorem, the number of steps is bounded by 5 times the number of decimal digits of the smaller input, making it very efficient.

Additional Resources

• Extended Euclidean Algorithm - Wikipedia
• Bézout's Identity - Wikipedia
• Modular Multiplicative Inverse - Wikipedia