The Euclidean Algorithm answers "what's the greatest
common divisor of a and b?" This page answers a sharper question the plain version leaves on the table:
which integers x and y actually produce that gcd, as a combination a·x + b·y =
gcd(a, b)? That such x and y always exist — for any integers a and b, not just nice ones — is
Bézout's identity. Finding them isn't a separate search: the same reduction loop that
finds the gcd, run with two extra numbers carried alongside, produces x and y for free.
The payoff is practical, not just theoretical: when gcd(a, m) = 1, the x this algorithm returns is (after one small adjustment — see Pitfalls) the modular inverse of a mod m — the number that plays the role of "1/a" in arithmetic where only remainders after dividing by m exist. Modular inverses are how RSA key generation and countless other modular-arithmetic algorithms divide without division.
Enter any two whole numbers (the algorithm strips the sign before starting, same as the plain version)
and step through the reduction. Watch the s and t columns build up alongside the
familiar r column — they carry the coefficients that will satisfy Bézout's identity once
r hits zero. 240, 46 is a classic textbook pair; 3, 11
finishes with gcd 1, so its x is directly a modular inverse.
Carry two running coefficients alongside the usual remainder, one pair per number in the reduction:
s tracks a's contribution, t tracks b's. Initialize so the invariant holds
trivially at the very first row — a itself is "0 reductions in," so its coefficient pair is
(1, 0) (that's just a = a·1 + b·0); b is (0, 1) the same
way. Every step of the plain algorithm replaces (old_r, r) with (r, old_r − q·r)
where q = ⌊old_r / r⌋ — the extended version applies the identical quotient to the
coefficient pairs: (old_s, s) → (s, old_s − q·s) and the same for t. Because
r's update and each coefficient's update use the same subtraction with the same q,
the relationship a·s + b·t = r that held at row zero keeps holding at every later row too — it's
an invariant carried forward by construction, not something checked after the fact.
row i: a·s_i + b·t_i = r_i (invariant, holds at every row)
row 0: a·1 + b·0 = a
row 1: a·0 + b·1 = b
row i+1: s_{i+1} = s_{i-1} − q_i·s_i, t_{i+1} = t_{i-1} − q_i·t_i, same q_i as rRun the loop to its usual end — r reaches 0, and the row just before it holds
gcd(a, b) in old_r, exactly as in the plain algorithm. The invariant says that same
row's old_s and old_t satisfy a·old_s + b·old_t = old_r = gcd(a, b) —
Bézout's identity, read straight off the last row the loop touches. No extra search, no back-substitution
through the whole trail of divisions by hand (the textbook-recursive way to teach this) — carrying two more
numbers through the same forward loop is enough.
function extGcd(a, b) {
const signA = a < 0 ? -1 : 1;
const signB = b < 0 ? -1 : 1;
a = Math.abs(a);
b = Math.abs(b);
let oldR = a, r = b;
let oldS = 1, s = 0;
let oldT = 0, t = 1;
while (r !== 0) {
const q = Math.floor(oldR / r);
[oldR, r] = [r, oldR - q * r];
[oldS, s] = [s, oldS - q * s];
[oldT, t] = [t, oldT - q * t];
}
// oldR = gcd(a, b); oldS, oldT solve it for the *absolute* a, b —
// flip sign to match whatever sign the caller actually passed in.
return { gcd: oldR, x: oldS * signA, y: oldT * signB };
}The x this returns is not automatically in the range a modular inverse needs — it can come out
negative, and JavaScript's % won't fix that for you. A modular inverse of a mod m is
conventionally reported in [0, m), but extGcd returns whichever x happens to fall
out of the reduction, sign and all. Take extGcd(3, 7): it returns x = -2. That's
a completely valid Bézout coefficient — 3·(-2) + 7·1 = 1 checks out — but it's not what most
callers mean by "the inverse of 3 mod 7," and x % 7 in JavaScript doesn't fix that for you:
-2 % 7 === -2, following the dividend's sign as always (the exact same JavaScript remainder
behavior the plain Euclidean Algorithm's own Pitfalls section warns about) — still negative, still outside
the [0, m) range a modular inverse is conventionally reported in. The fix is the same
double-add-and-mod normalization used anywhere a possibly-negative value needs folding into
[0, m): ((x % m) + m) % m. For x = -2, m = 7 that's
((-2 % 7) + 7) % 7 = (-2 + 7) % 7 = 5 — checked directly: 3 × 5 = 15 = 2×7 + 1, so
5 really is 3's inverse mod 7. Verified this normalization (and the un-normalized failure it fixes) across
every coprime pair 1 ≤ a, m < 200 — 24,104 coprime pairs out of 39,402 checked total, zero
mismatches after normalizing, and confirmed the algorithm correctly reports "no inverse exists" (via
gcd ≠ 1) on all 15,298 non-coprime pairs in the same sweep, rather than silently returning a
wrong answer.
x and y aren't unique — the algorithm hands back exactly one solution out of infinitely many.
Given any solution (x₀, y₀), every pair (x₀ + k·(b/g), y₀ − k·(a/g)) for integer k
also satisfies Bézout's identity, where g = gcd(a, b) — shifting x by a whole multiple of b/g and y by the
matching multiple of a/g cancels out exactly, leaving a·x + b·y unchanged. Checked directly on
the demo's classic pair: extGcd(240, 46) returns (x, y) = (-9, 47); stepping k = 1 gives
(-9 + 46/2, 47 − 240/2) = (14, -73), and indeed 240×14 + 46×(-73) = 3360 − 3358 = 2,
the same gcd. A caller who assumes the returned pair is the answer — say, expecting a specific x on
repeated calls, or comparing two independent implementations' output directly — will be surprised the moment
either implementation takes a different reduction path.
O(log(min(a, b))) division steps — identical bound to the plain Euclidean Algorithm, and for the same reason: the extended version runs exactly the same sequence of divisions, just carrying two more running numbers through each one. Those extra multiply-and-subtract updates are O(1) work per step, so they add a constant factor, not a new term — the step count itself, and therefore the Fibonacci-pair worst case proven on the plain algorithm's own page, carries over unchanged.
This site's guide, Choosing a Number Theory Algorithm, compares this entry against the other thirteen Number Theory entries side by side.