Extended Euclidean Algorithm
Also finds x, y with ax + by = gcd(a, b) by carrying coefficients back up the division table; the route to modular inverses.
Decision · step 2 of 8Extended Euclid: gcd(48, 18) with coefficients
Row 0: 48 = 2 x 18 + 12. Next row: a = 18, b = 12, the divisor and the remainder.
What you will see
Coefficient columns update alongside the remainders; back-substitution is shown as the table unwinds.
Cost
| Best | O(1) |
|---|---|
| Average | O(log min(a, b)) |
| Worst | O(log min(a, b)) |
| Space | O(1) |
How you work with it here
play it through, step one change at a time, run it on your own input.
Screen readers: Numbers announce their value and role; each step announces the arithmetic performed.
Reduced motion: Values crossfade; no travelling digits.