Bezout Identity Calculator
Find integers x and y satisfying Bezout's identity: ax + by = gcd(a, b).
Enter Numbers
Bezout's Identity Theorem
For any integers a and b (not both zero), there exist integers x and y such that:
The coefficients x and y are called Bezout coefficients.
Properties
- Bezout coefficients are not unique
- If (x₀, y₀) is a solution, all solutions are:
- x = x₀ + (b/d)k
- y = y₀ - (a/d)k
- where d = gcd(a, b) and k is any integer
Bezout Identity
35(1) + 15(-2) = 5
General Solution
x = 1 + 3k
y = -2 - 7k
where k is any integer
Sample Coefficient Pairs
| k | x | y | ax+by |
|---|---|---|---|
| -5 | -14 | 33 | 5 |
| -4 | -11 | 26 | 5 |
| -3 | -8 | 19 | 5 |
| -2 | -5 | 12 | 5 |
| -1 | -2 | 5 | 5 |
| 0 | 1 | -2 | 5 |
| 1 | 4 | -9 | 5 |
| 2 | 7 | -16 | 5 |
| 3 | 10 | -23 | 5 |
| 4 | 13 | -30 | 5 |
| 5 | 16 | -37 | 5 |
Verification
35 × (1) + 15 × (-2) = 5
Identity verified
What Is Bézout's Identity?
Bézout's identity is a fundamental theorem in number theory: for any two integers a and b (not both zero), there exist integers x and y such that ax + by = gcd(a,b). This means the greatest common divisor can be written as an integer linear combination of the two original numbers. The values x and y are called Bézout coefficients. This calculator computes the GCD via the extended Euclidean algorithm, returns the Bézout coefficients, and verifies the identity by plugging them back into the original equation.
The theorem generalizes: for any number of integers a₁, a₂, ..., aₙ, there exist coefficients x₁, x₂, ..., xₙ such that Σ aᵢxᵢ = gcd(a₁, ..., aₙ). Bézout's identity underpins modular arithmetic, the Chinese Remainder Theorem, and all of computational number theory.
Extended Euclidean Algorithm
The extended Euclidean algorithm computes the GCD while tracking the coefficients. It builds on the observation that if gcd(a,b) = gcd(b, a mod b), and we know coefficients for (b, a mod b), we can derive them for (a,b).
Extended Euclidean Recursion
Where:
- a, b= The two input integers. The algorithm recursively reduces (a,b) to (b, a mod b)
- x, y= The Bézout coefficients — satisfy a×x + b×y = gcd(a,b)
Understanding the Results
| Output | Description |
|---|---|
| GCD | The greatest common divisor of a and b — always positive |
| Bézout Coefficients x, y | Integers such that a×x + b×y = GCD |
| Verification | a×x + b×y computed to confirm it equals the GCD |
| Step-by-step | Each recursive step shows (a, b), quotient, and the accumulating x,y values |
How to Use This Calculator
- Enter a and b: Type any two integers (not both zero). The calculator uses their absolute values for the GCD computation.
- Read the identity: The calculator displays gcd(a,b) and the Bézout coefficients x and y.
- Verify: The verification card shows a×x + b×y computed numerically — it should equal the GCD (within floating-point tolerance).
- Study the steps: The step-by-step panel traces the recursive extended Euclidean algorithm at each level.
Real-World Applications
Bézout's identity directly enables modular inversion in cryptography. When gcd(a, n) = 1, the x coefficient satisfies a×x ≡ 1 (mod n) — this is how RSA decryption exponents are computed. In linear Diophantine equations ax + by = c, solutions exist if and only if gcd(a,b) divides c; Bézout gives the fundamental solution that all others are built from. In computer algebra systems, Bézout is used for polynomial GCD computation and partial fraction decomposition. In error-correcting codes, Reed-Solomon decoding uses the Euclidean algorithm over polynomial rings, which is Bézout applied to polynomials instead of integers.
Worked Examples
Bézout for 35 and 15
Problem:
Find integers x and y such that 35x + 15y = gcd(35, 15).
Solution Steps:
- 1Enter a = 35, b = 15.
- 2gcd(35,15): 35=2×15+5; 15=3×5+0 → gcd=5.
- 3Extended algorithm: 35 × 1 + 15 × (−2) = 35 − 30 = 5.
- 4Verification: 35×1 + 15×(−2) = 5 ✓.
Result:
gcd(35, 15) = 5, x = 1, y = −2. 35(1) + 15(−2) = 35 − 30 = 5.
Coprime Case
Problem:
Find Bézout coefficients for a = 17, b = 31.
Solution Steps:
- 1Enter a = 17, b = 31. Since gcd(17,31) = 1, they are coprime.
- 2Extended Euclidean gives x = 11, y = −6.
- 3Verification: 17×11 + 31×(−6) = 187 − 186 = 1 ✓.
Result:
gcd(17, 31) = 1, x = 11, y = −6. The modular inverse of 17 mod 31 is 11 (since 17×11 ≡ 1 mod 31).
Tips & Best Practices
- ✓If gcd(a,b) = 1, the x coefficient is the modular inverse of a modulo b — a crucial fact for cryptography.
- ✓The extended Euclidean algorithm is a recursive function that builds up coefficients from the base case (b=0, gcd=a).
- ✓For very large numbers, the algorithm runs in O(log min(a,b)) steps — it's extremely efficient.
- ✓Bézout's identity holds for any finite set of integers as well — iteratively apply the two-number version.
Frequently Asked Questions
Sources & References
Last updated: 2026-06-06
Help us improve!
How would you rate the Bezout Identity Calculator?
Editorial Note
MyCalcBuddy Editorial Team
This page is maintained as an educational calculator reference.
Formula Source: Handbook of Mathematical Functions
by Abramowitz & Stegun