The Extended Euclidean Algorithm
Here is an old puzzle, sometimes told with two water jugs: you have an unlimited supply of
water, a 30-litre jug and an 18-litre jug,
and you may fill, empty, or pour between them as many times as you like. What amounts can you
ever measure out exactly? It turns out the answer is: exactly the multiples of
\gcd(30, 18) = 6 litres — and remarkably, there is a precise recipe
telling you exactly how many times to fill and empty each jug to get there.
Bézout's identity
promises that recipe exists: integers x, y with
ax + by = \gcd(a,b). But it doesn't say how to find
x and y. The
extended Euclidean algorithm answers that: it runs
Euclid's
algorithm as usual, then walks the steps backward to reveal the coefficients. It is
the computational heart of the whole course.
Notice what a leap this is from the plain Euclidean algorithm. That algorithm only ever tells
you the size of the largest shared measure of a and
b — a single number. The extended version tells you exactly
how to build that number out of a and
b themselves, using only addition, subtraction, and multiplication by
whole numbers. That extra "recipe," not just the final gcd, is what every application in this
page actually needs.
Yes — and rather famously. In the film Die Hard: With a Vengeance (1995), the heroes
must defuse a bomb by measuring out exactly 4 gallons of water using
only a 5-gallon jug and a 3-gallon jug,
with a countdown ticking. It's a real instance of the water-jug puzzle from the top of this
page — and it works precisely because
\gcd(5, 3) = 1, so every whole number of gallons, including
4, is reachable.
The extended Euclidean algorithm hands you the recipe directly:
5\cdot 2 + 3\cdot(-2) = 4, meaning "fill the 5-gallon jug twice over,
and pour away the equivalent of two 3-gallon jugs' worth" — which is exactly the fill-pour-empty
sequence that gets the job done. No trial and error required, and certainly no on-screen
countdown necessary once you know the algorithm.
Worked example — fully tracing \gcd(30, 18)
First, run the ordinary Euclidean algorithm all the way to the end:
\begin{aligned}
30 &= 18 \cdot 1 + 12 \\
18 &= 12 \cdot 1 + 6 \\
12 &= 6 \cdot 2 + 0
\end{aligned}
The last non-zero remainder is 6, so
\gcd(30, 18) = 6 — that part is nothing new. Now rearrange each
division line (except the last, which has nothing left to isolate) to solve for its remainder:
\begin{aligned}
12 &= 30 - 18\cdot 1 \\
6 &= 18 - 12\cdot 1
\end{aligned}
Starting from the bottom equation, substitute the first equation's expression for
12 in place of 12, working strictly
backward up the list until only 30 and
18 remain:
\begin{aligned}
6 &= 18 - 12 \\
&= 18 - (30 - 18\cdot 1) \\
&= 18 - 30 + 18 \\
&= 30\cdot(-1) + 18\cdot 2.
\end{aligned}
So x = -1 and y = 2. Always check by
substituting back into the original combination:
30\cdot(-1) + 18\cdot 2 = -30 + 36 = 6 — exactly
\gcd(30, 18), as promised. Translated back to the jugs: fill the
18-litre jug twice and "empty" the 30-litre jug once (in the sense of subtracting a 30-litre
fill), and the net water measured is 6 litres.
The forward (table) version
Back-substitution is fiddly to automate — you need to remember every intermediate equation and
rewind through them in the right order. The slicker form carries the coefficients
forward alongside the remainders, in a single left-to-right pass, so nothing needs to
be remembered and rewound. Keep a running pair (x, y) for each
remainder so that r = ax + by holds on every row, and update them
with the very same quotient q that Euclid's algorithm uses at that
step:
\begin{aligned}
r_{\text{new}} &= r_{\text{old}} - q\, r_{\text{cur}} \\
x_{\text{new}} &= x_{\text{old}} - q\, x_{\text{cur}} \\
y_{\text{new}} &= y_{\text{old}} - q\, y_{\text{cur}}
\end{aligned}
Seed the table with (a; 1, 0) and (b; 0, 1)
— these simply record the truisms a = a\cdot 1 + b\cdot 0 and
b = a\cdot 0 + b\cdot 1. When the remainder column hits
0, the previous row holds the gcd together with its Bézout
coefficients, computed in one forward sweep with no backtracking at all. This is the version
almost every computer implementation actually uses.
Run it on the same pair, a=30 and b=18, as a check:
\begin{aligned}
(r, x, y) &= (30,\ 1,\ 0) \\
(r, x, y) &= (18,\ 0,\ 1) \\
q=1:\quad (r, x, y) &= (12,\ 1,\ -1) \\
q=1:\quad (r, x, y) &= (6,\ -1,\ 2) \\
q=2:\quad (r, x, y) &= (0,\ 3,\ -5) \quad\text{stop}
\end{aligned}
The row just before the remainder hit 0 reads
(6, -1, 2) — the same x=-1,
y=2 found by back-substitution above, arrived at with no
substitution or rewinding at all, just one table filled in top to bottom.
Why we care: modular inverses
The killer application: when \gcd(a, n) = 1, the algorithm produces
x, y with
ax + ny = 1 \quad\Longrightarrow\quad ax \equiv 1 \pmod{n}.
That x is the modular inverse
of a — the number you "divide by" in clock arithmetic, where ordinary
division doesn't exist. Finding inverses quickly is exactly what makes RSA decryption,
Diffie–Hellman key exchange, and a hundred other algorithms practical.
A concrete example: find the inverse of 7 modulo
30. Run the extended algorithm on (30, 7):
\begin{aligned}
30 &= 7\cdot 4 + 2 \\
7 &= 2\cdot 3 + 1 \\
2 &= 1\cdot 2 + 0
\end{aligned}
Back-substitute for the gcd, 1:
\begin{aligned}
1 &= 7 - 2\cdot 3 \\
&= 7 - (30 - 7\cdot 4)\cdot 3 \\
&= 7\cdot 13 + 30\cdot(-3).
\end{aligned}
So 7\cdot 13 + 30\cdot(-3) = 1, which means
7\cdot 13 \equiv 1 \pmod{30}. Check it directly:
7 \times 13 = 91 = 3\times 30 + 1 — remainder
1, exactly as required. The inverse of 7
modulo 30 is 13, found without ever
listing every multiple of 7 and checking each one by hand.
Two loose ends worth tying off. First, the coefficient y=-3 found
along the way is thrown away here — only x matters for the inverse.
Second, x and x + 30 and
x - 30 all satisfy the same congruence, so by convention the inverse
is always reported reduced to the range 0 \le x < n — here,
13 itself already sits in [0, 30), so no
adjustment was needed. And if \gcd(a, n) \ne 1, the algorithm still
runs perfectly well — it just returns a gcd bigger than 1, which is
exactly the signal that no inverse exists at all.
Back-substitution is where almost everyone trips up — not on the arithmetic, but on the
order. You must eliminate remainders starting from the most recently
produced one and work strictly backward toward the original two numbers. Skip a line, or
substitute in the wrong direction, and the coefficients come out wrong even though every
individual step "looks" like valid algebra.
A concrete trap: with the (30, 18) example above, it's tempting to
substitute the first equation (12 = 30 - 18\cdot 1) into the
gcd line before rearranging the second equation for 6. But
the gcd line is 6 = 18 - 12\cdot 1 — it contains
18 and 12, not 30
and 18 yet. Substitute for 12 too early or
twice, and a stray 18 or 12 gets left
behind in the final line, silently ruining the answer. The safe habit: always eliminate the
largest-indexed remainder still present in your current expression, one at a time,
until only a and b remain — then verify by
plugging x and y back into
ax + by and confirming it equals the gcd exactly.
Two methods, one answer
Step back and there are really just two moving parts to this whole page. First,
back-substitution: run Euclid's algorithm forward to get the gcd, then walk the
division lines backward, in strict reverse order, until the coefficients of
a and b fall out. Second, the
forward table: carry running coefficients alongside the remainders from the
very first step, so the answer is simply sitting there — no rewinding — the moment the
remainder reaches 0. Both methods, run on the very same
(30, 18), landed on the identical answer,
x=-1, y=2 — which is exactly the point: Bézout's identity guarantees
a solution exists, and the extended Euclidean algorithm is simply a reliable way to compute it,
whichever bookkeeping style you prefer.
Every time your browser shows a little padlock next to a web address, this exact algorithm has
almost certainly just run. RSA encryption — one of the workhorses of internet security — needs
to generate a private key d that is the modular
inverse of a public number e, modulo some large number
\varphi(n) built from two enormous secret primes. Finding that inverse
is precisely the job the extended Euclidean algorithm was built for — except the numbers
involved are hundreds of digits long, not two-digit toy examples.
The reason this matters for speed is worth pausing on. Trying every possible inverse by brute
force on numbers that size would take longer than the age of the universe. The extended
Euclidean algorithm finds it in a fraction of a second, because — just like the ordinary
Euclidean algorithm — the numbers shrink by roughly a constant factor at every single step. So
this two-thousand-year-old idea, dressed up with a backward pass for coefficients, quietly
secures online banking, encrypted messaging, and pretty much every "https" connection made
today, millions of times a second, all over the world.
It isn't only RSA, either. Diffie–Hellman key exchange, elliptic-curve cryptography, and error-
correcting codes used in satellite links and QR codes all lean on modular inverses somewhere
under the hood — and every one of them reaches for the same two-thousand-year-old backward pass
to compute them.