Extended Euclidean Algorithm Calculator
Find GCD and Bézout coefficients x, y such that ax + by = gcd(a, b).
About Extended Euclidean Algorithm Calculator
The Extended Euclidean Algorithm not only finds gcd(a, b) but also integers x and y satisfying Bézout's identity: ax + by = gcd(a, b). These coefficients are used to compute modular inverses, solve linear Diophantine equations, and in the Chinese Remainder Theorem. The algorithm extends each step of the basic Euclidean algorithm by tracking how the GCD is expressed as a linear combination of a and b.
Formula
Bézout's identity
ax + by = gcd(a, b) for some integers x, y
- a
- First integer
- b
- Second integer
- x
- First Bézout coefficient
- y
- Second Bézout coefficient
Worked example
With the default values below, Extended Euclidean Algorithm Calculator returns GCD of 2. Change any input above and every figure here is recalculated in your browser.
Inputs used
- a
- 240
- b
- 46
Results
- GCD
- 2
- Bézout coefficient x
- -9
- Bézout coefficient y
- 47
- Bézout's Identity
- 240 × (-9) + 46 × (47) = 2
Step by step
- 1Step 1
- 2Step 2
- 3Step 3
- 4Step 4
- 5Step 5
- 6Bézout's identity
Assumptions and limits
- The result is derived only from the 2 inputs listed above. Anything not among them is not part of the calculation.
- In particular, this calculator does not take inflation, tax, fees or charges or compounding frequency into account.
- Figures are rounded for display to whole numbers, so totals built from several rounded parts can differ slightly from the unrounded arithmetic.
How these calculators are built and tested is described on the Methodology page. If a figure looks wrong, please report it.
Frequently Asked Questions
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. The algorithm returns the pair with smallest |x|.
How does this relate to modular inverses?
If gcd(a, m) = 1, then ax + my = 1. Reducing mod m gives ax ≡ 1 (mod m), so x mod m is the modular inverse of a. The extended algorithm directly computes it.