Euclid’s algorithm finds gcd(a, b) by repeated remainders. The extended version tracks a little more and gets a powerful bonus: the integers x and y satisfying Bézout’s identitya·x + b·y = gcd(a, b). Those coefficients are the workhorse of number theory — they give modular inverses (the key to RSA decryption and division mod n) and they’re how the Chinese Remainder Theorem stitches congruences together. Step through the coefficient table and watch a·x + b·y = gcd hold at every single row.
O(log min(a,b)) · returns gcd AND x, y with a·x + b·y = gcd · powers modular inverses & CRT
gcd
The greatest common divisor of a and b — the largest integer dividing both.
Bézout identity
There always exist integers x, y with a·x + b·y = gcd(a, b).
the table
Track (r, s, t) so that a·s + b·t = r holds on every row, down to r = gcd.
modular inverse
If gcd(a, m) = 1, then x from a·x + m·y = 1 is a⁻¹ mod m.
extgcd.js — the coefficients come free
Ready
Computing gcd(240, 46) and the Bézout coefficients. We keep a table of (r, s, t) where 240·s + 46·t = r on every row. Each step subtracts q copies of the row above. Step to build it.
–
current r
–
quotient q
✓
identity holds
How it works
Ordinary Euclid replaces (a, b) with (b, a mod b) until the second term is 0; the last nonzero value is the gcd. The extended version carries two extra columns, s and t, initialized so that the first two rows read a = a·1 + b·0 and b = a·0 + b·1. Then every step subtracts q copies of the previous row from the one before it — applied to all three columns at once. Because the same linear combination is applied to r, s, and t together, the invariant a·s + b·t = r is preserved automatically. When r reaches the gcd, that row’s s and t are the Bézout coefficients x and y.
1
Seed two rows
Start with (r=a, s=1, t=0) and (r=b, s=0, t=1). Each already satisfies a·s + b·t = r trivially.
2
Subtract q copies of the previous row
Compute q = ⌊r_prev₂ / r_prev₁⌋ and form a new row = row₂ − q·row₁, applied to r, s, and t together. The remainder r shrinks just like plain Euclid.
3
The identity is preserved
Because the same combination hits all three columns, a·s + b·t = r stays true on the new row. Repeat until r = 0.
✓
Read off gcd and coefficients
The last row with r ≠ 0 gives gcd = r and its s, t are the Bézout coefficients x, y with a·x + b·y = gcd. If gcd = 1, x is the modular inverse of a mod b.
Time
O(log min(a,b))
Returns
gcd + x, y
Invariant
a·s + b·t = r
Powers
inverses, CRT
The code
# extended Euclid: gcd and x, y with a*x + b*y = gcddef extgcd(a, b):
old_r, r = a, b
old_s, s = 1, 0
old_t, t = 0, 1
while r != 0:
q = old_r // r
old_r, r = r, old_r - q * r # same q applied
old_s, s = s, old_s - q * s # to all three
old_t, t = t, old_t - q * t # columnsreturn old_r, old_s, old_t # gcd, x, y# modular inverse of a mod m (when gcd(a, m) = 1):# g, x, _ = extgcd(a, m); inverse = x % m
Quick check
1. Besides the gcd, what does the extended Euclidean algorithm return?
It returns the Bézout coefficients x and y satisfying a·x + b·y = gcd(a, b). These are what make it useful beyond plain gcd — they give modular inverses and drive the Chinese Remainder Theorem.
2. How do the Bézout coefficients give a modular inverse?
When gcd(a, m) = 1, extended Euclid gives a·x + m·y = 1. Taking this mod m kills the m·y term, leaving a·x ≡ 1 (mod m). So x (reduced mod m) is the modular inverse of a.
3. Why does the invariant a·s + b·t = r stay true through the algorithm?
Each step forms a new row as row₂ − q·row₁ across all three columns simultaneously. Since r, s, and t undergo the identical combination, a·s + b·t = r is preserved on the new row automatically.
FAQ
What is the extended Euclidean algorithm?
An extension of Euclid’s algorithm that computes gcd(a, b) and also integers x, y with a·x + b·y = gcd(a, b) (the Bézout coefficients), in O(log min(a, b)) time by carrying two extra coefficient columns alongside the remainder.
How is it used to find a modular inverse?
To invert a mod m (when gcd(a, m) = 1), run extended Euclid on a and m to get a·x + m·y = 1; reducing mod m gives a·x ≡ 1, so x mod m is the inverse. This underlies modular division and RSA (the private exponent is the inverse of the public one mod φ(n)).
What is the Chinese Remainder Theorem and how does it relate?
CRT says a system x ≡ aᵢ (mod nᵢ) with pairwise-coprime moduli has a unique solution modulo the product of the nᵢ. Building that solution needs modular inverses (invert the product of the other moduli), which come from extended Euclid — so it’s the engine inside CRT.
Where are these used in practice?
Cryptography and computer algebra: RSA key generation and CRT-accelerated decryption (~4× faster), Diffie–Hellman, modular arithmetic libraries, error-correcting codes, and hashing — anywhere you divide modulo a number or combine information across coprime moduli.