AlgoScope

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.

Mathematics, algorithm, intermediate
Row 0: 48 equals 2 times 18 plus 12.abqrxy0124818212
Row 0: 48 equals 2 times 18 plus 12.abqrxy0124818212

Extended Euclid: gcd(48, 18) with coefficients

Decision, step 2 of 8

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)

Leads to

Topics that need this one first.