Extended Euclidean Algorithm Calculator
Find GCD and Bezout coefficients (x, y) such that ax + by = gcd(a, b).
Enter Numbers
Algorithm Steps
| Step | q | r | s | t |
|---|---|---|---|---|
| 0 | - | 240 | 1 | 0 |
| 1 | - | 46 | 0 | 1 |
| 2 | 5 | 10 | 1 | -5 |
| 3 | 4 | 6 | -4 | 21 |
| 4 | 1 | 4 | 5 | -26 |
| 5 | 1 | 2 | -9 | 47 |
| 6 | 2 | 0 | 23 | -120 |
Algorithm
The extended algorithm finds x, y such that:
ax + by = gcd(a, b)
Recurrence relations:
rᵢ = rᵢ₋₂ - qᵢrᵢ₋₁
sᵢ = sᵢ₋₂ - qᵢsᵢ₋₁
tᵢ = tᵢ₋₂ - qᵢtᵢ₋₁
Greatest Common Divisor
GCD = 2
GCD
2
LCM
5520
Bezout Coefficients
x
-9
y
47
Bezout Identity
240 × (-9) + 46 × (47) = 2
Verification: Correct
Applications
- Finding modular multiplicative inverse
- Solving linear Diophantine equations
- RSA cryptography key generation
- Computing continued fractions