Bezout's Identity Calculator
Find the Bezout coefficients x and y such that ax + by = gcd(a, b) using the Extended Euclidean Algorithm.
Input Numbers
Find integers x, y such that: 56x + 15y = gcd(56, 15)
Bezout's Identity
1 = -4(56) + 15(15)
gcd(56, 15)
1
x
-4
y
15
Verification
56(-4) + 15(15) = 1
Algorithm Steps
| Step | r | s | t |
|---|---|---|---|
| 0 | 56 | 1 | 0 |
| 1 | 15 | 0 | 1 |
| 2 | 11 | 1 | -3 |
| 3 | 4 | -1 | 4 |
| 4 | 3 | 3 | -11 |
| 5 | 1 | -4 | 15 |
Other Representations
1 = (-34)(56) + (127)(15)
1 = (-19)(56) + (71)(15)
1 = (11)(56) + (-41)(15)
1 = (26)(56) + (-97)(15)
Bezout's Identity
Theorem
For any integers a and b, there exist integers x and y such that ax + by = gcd(a, b).
Applications
- Solving linear Diophantine equations
- Finding modular multiplicative inverses
- RSA cryptography
What Is Bézout's Identity?
Bézout's identity states that for any two non-zero integers a and b, there exist integers x and y such that ax + by = gcd(a,b). In other words, the greatest common divisor of a and b can be expressed as a linear combination of a and b. This calculator uses the extended Euclidean algorithm to find both the GCD and the Bézout coefficients x and y, showing the full step-by-step computation.
The identity is named after the 18th-century French mathematician Étienne Bézout, though the result was known earlier. It's a cornerstone of elementary number theory with practical applications in cryptography (computing modular inverses for RSA), solving linear Diophantine equations, and simplifying fractions. The calculator handles both positive and negative inputs, computing the GCD of the absolute values and adjusting the coefficients for the original signs.
Extended Euclidean Algorithm
The extended Euclidean algorithm maintains three sequences — remainders (r), s-coefficients, and t-coefficients — updating them with quotients at each step until the remainder reaches zero. The GCD is the last non-zero remainder, and its s and t values are the Bézout coefficients.
Extended Euclidean Algorithm Recurrence
Where:
- a, b= The two input integers — can be positive, negative, or zero
- q= The integer quotient at each step — floor(r_{i−2} / r_{i−1})
- s, t= The Bézout coefficients — satisfy s×a + t×b = gcd(a,b)
Understanding the Results
| Output | Description |
|---|---|
| GCD(a,b) | The greatest common divisor — always positive. For (56, 15), gcd = 1. |
| Bézout Identity | The linear combination: e.g., −4×56 + 15×15 = 1 for a=56, b=15. |
| Coefficients x, y | The x and y that satisfy ax + by = gcd(a,b) |
| Step-by-step table | Each iteration shows r, s, t, the quotient q, and the corresponding linear combination equation |
How to Use This Calculator
- Enter a and b: Type two integers. Both can be positive, negative, or zero (but not both zero).
- View the GCD: The calculator computes the GCD and displays the Bézout identity.
- Explore the steps: The step-by-step table shows each iteration of the extended Euclidean algorithm with the values of r, s, t, q, and the linear combination equation at each stage.
Real-World Applications
Bézout's identity is the workhorse behind modular inverses. When gcd(a, n) = 1, the extended Euclidean algorithm finds x such that ax ≡ 1 (mod n) — that is, the modular inverse of a modulo n. This is how RSA private keys are generated: the decryption exponent d is the modular inverse of the public exponent e modulo φ(n). Without Bézout, public-key cryptography would be impossible.
In Diophantine equation solving, Bézout's identity tells you whether ax + by = c has integer solutions: solutions exist if and only if gcd(a,b) divides c. In Chinese Remainder Theorem computations, Bézout coefficients are used to combine modular congruences. In fraction simplification, dividing numerator and denominator by their GCD reduces a fraction to lowest terms.
Worked Examples
Bézout for 56 and 15
Problem:
Find gcd(56, 15) and express it as a linear combination 56x + 15y = gcd.
Solution Steps:
- 1Enter a = 56, b = 15.
- 2Extended Euclidean: 56 = 1×56 + 0×15; 15 = 0×56 + 1×15; 56 − 3×15 = 11 → r=11, s=1, t=−3; 15 − 1×11 = 4 → r=4, s=−1, t=4; 11 − 2×4 = 3 → r=3, s=3, t=−11; 4 − 1×3 = 1 → r=1, s=−4, t=15.
- 3GCD = 1. Bézout: (−4)×56 + 15×15 = −224 + 225 = 1.
Result:
gcd(56, 15) = 1, x = −4, y = 15. The modular inverse of 15 mod 56 is 15 (since 15×15 ≡ 1 mod 56).
Tips & Best Practices
- ✓The quotient q = floor(r_{i-2} / r_{i-1}) at each step — this is integer division rounding toward negative infinity.
- ✓Coefficients x and y are not unique — they form an infinite family: (x + k·b/gcd, y − k·a/gcd) for any integer k.
- ✓If gcd(a,b) = 1, the numbers are coprime and each has a modular inverse modulo the other.
- ✓The step-by-step table traces every iteration — use it to learn the algorithm or verify manual computations.
Frequently Asked Questions
Sources & References
Last updated: 2026-06-06
Help us improve!
How would you rate the Bezout's Identity Calculator?
Related Calculators
Editorial Note
MyCalcBuddy Editorial Team
This page is maintained as an educational calculator reference.
Formula Source: Handbook of Mathematical Functions
by Abramowitz & Stegun