Extended Euclidean Algorithm Calculator
Find GCD and Bézout coefficients x, y such that ax + by = gcd(a, b).
Inputs
First integer.
Second integer.
GCD
2
Bézout coefficient x
-9
Bézout coefficient y
47
Bézout's Identity
240 × (-9) + 46 × (47) = 2
Step by step
Step 1
240 = 5 × 46 + 10
Step 2
46 = 4 × 10 + 6
Step 3
10 = 1 × 6 + 4
Step 4
6 = 1 × 4 + 2
Step 5
4 = 2 × 2 + 0
Bézout's identity
240 × (-9) + 46 × (47) = 2
How it works
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
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.