What does the extended Euclidean algorithm compute?

It computes gcd(a, b) exactly like the standard Euclidean algorithm, but additionally finds integers x and y (the Bézout coefficients) satisfying a×x + b×y = gcd(a, b).

What is Bézout's identity?

Bézout's identity states that for any two integers a and b, there exist integers x and y such that a×x + b×y = gcd(a, b) — the extended Euclidean algorithm is the standard way to find them.

Are the Bézout coefficients unique?

No — if (x, y) is one solution, then (x + k×(b/gcd), y − k×(a/gcd)) is also a solution for any integer k. This calculator returns the specific pair produced by the standard algorithm.

Can a or b be negative?

Yes, the algorithm handles negative integers correctly; the reported gcd is always returned as a non-negative number, with x and y adjusted accordingly.

What if a and b are coprime?

If gcd(a, b) = 1, the equation becomes a×x + b×y = 1, meaning x is exactly the modular multiplicative inverse of a modulo b (and y is the inverse of b modulo a).

How does this relate to the Modular Multiplicative Inverse Calculator?

The Modular Multiplicative Inverse Calculator runs this exact algorithm internally and extracts x, reduced modulo m, as the answer — this calculator exposes the full gcd and both coefficients directly.

How large can a and b be?

This calculator supports integers up to 100 digits each, computed with exact BigInt arithmetic so there's no floating-point rounding error even for huge inputs.

Where is the extended Euclidean algorithm used in real life?

It's used in RSA key generation, solving linear Diophantine equations, computing modular inverses for cryptographic protocols, and any algorithm that needs an explicit certificate for a computed gcd.

Extended Euclidean Algorithm Calculator — Find gcd(a,b) and Bézout Coefficients

Our Extended Euclidean Algorithm Calculator finds not just gcd(a, b), but also integers x and y — the Bézout coefficients — satisfying the identity a×x + b×y = gcd(a, b), computed with BigInt precision for arbitrarily large inputs. It's the direct engine behind the site's Modular Multiplicative Inverse Calculator and countless other number-theoretic algorithms.

Quick Answer

This calculator finds gcd(a, b) plus integers x and y satisfying a×x + b×y = gcd(a, b), using the extended Euclidean algorithm with exact BigInt precision.

Enter a and b, then click Calculate.

How to Use the Extended Euclidean Algorithm Calculator — gcd + Bézout Coefficients

1
Enter two integers, a and b.
2
Click 'Calculate' to find gcd(a, b) and the Bézout coefficients x and y.
3
Verify the result: a × x + b × y always equals the computed gcd.

Why Use Extended Euclidean Algorithm Calculator — gcd + Bézout Coefficients?

The ordinary Euclidean algorithm finds gcd(a, b) by repeated division, but the extended version tracks extra bookkeeping at each step so that, by the time it finishes, it has also expressed that gcd as a linear combination of the original a and b — integers x and y with a×x + b×y = gcd(a, b), a result guaranteed to exist by Bézout's identity. This isn't just a mathematical curiosity: those coefficients are exactly what's needed to compute modular multiplicative inverses, solve linear Diophantine equations, and implement RSA key generation.

Frequently Asked Questions

Related Tools

Modular Multiplicative Inverse Calculator — Solve ax ≡ 1 (mod m)

Find the modular multiplicative inverse of a modulo m using the extended Euclidean algorithm. Free calculator with BigInt precision and existence check.

Chinese Remainder Theorem Calculator — Solve Modular Systems

Solve a system of congruences x ≡ aᵢ (mod mᵢ) for pairwise-coprime moduli using the Chinese Remainder Theorem. Free calculator with BigInt precision.

Modular Exponentiation Calculator — Fast bᵉ mod m Online

Calculate bᵉ mod m for arbitrarily large exponents using fast square-and-multiply exponentiation. Free calculator with BigInt precision, essential for cryptography.

Continued Fraction Calculator — Expand & Evaluate Online

Expand any decimal number or fraction into its continued fraction terms [a₀; a₁, a₂, ...] and see every convergent. Free calculator with exact BigInt precision.