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.
Extended Euclid: gcd(48, 18) with coefficients
Row 0: 48 = 2 x 18 + 12. Next row: a = 18, b = 12, the divisor and the remainder.
Cost
- Best
- O(1)
- Average
- O(log min(a, b))
- Worst
- O(log min(a, b))
- Space
- O(1)
Before this
Leads to
Topics that need this one first.