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