Extended Euclidean Algorithm & Modular Inverse

extgcd(a, m) finds x, y with a·x + m·y = gcd(a, m). When gcd = 1, the Bezout x is the modular inverse a−1 mod m.

forward step 0

Euclidean table (a, b, q, r)

current step gcd row
Press Step to run the forward Euclidean division.

Back-substitution: building x, y

Modular inverse appears here once gcd(a, m) = 1.

Back-substitution chain: assembling a·x + m·y = gcd

Each row of the iteration already carries the identity r = s·a + t·m. We replay them from the top so you can watch the remainder shrink while the coefficients s and t grow toward the final Bezout pair. Once r = gcd, those coefficients are x and y.

    We compute gcd(a, m) by repeated division (forward phase), then substitute backward to express the gcd as a·x + m·y. If gcd = 1, x mod m is the inverse.
    Self-contained visualization. Coefficients use the iterative invariant r = s·a + t·b: each row stores (r, s, t) so when r reaches 0 the previous row is (gcd, x, y). The inverse exists iff gcd(a, m) = 1. See junior.md and professional.md for the proofs.