Extended Euclidean Algorithm

Extends Euclid's GCD to also find integers x, y satisfying Bézout's identity ax + by = gcd(a,b). Computed by unwinding the recursive GCD calls and back-substituting coefficients on the way up.

Category

Mathematics

Time complexity

O(log min)

Space complexity

O(log min)

Pseudocode

extgcd(a, 0) = (a, 1, 0)
extgcd(a, b): recurse on (b, a mod b) → (g, x₁, y₁)
x = y₁
y = x₁ − ⌊a/b⌋·y₁

Reference implementation

def extgcd(a, b):
    if b == 0: return a, 1, 0
    g, x1, y1 = extgcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

Open the interactive Extended Euclidean Algorithm visualisation →