The Extended Euclidean Algorithm
Bézout's identity
promises integers x, y with
ax + by = \gcd(a,b) — but how do you actually find them? The
extended Euclidean algorithm answers this: 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.
Back-substitution
Recall the run of Euclid's algorithm
on (48, 18). Rearrange each line to isolate its remainder:
\begin{aligned}
48 = 18\cdot 2 + 12 &\;\Rightarrow\; 12 = 48 - 18\cdot 2 \\
18 = 12\cdot 1 + 6 &\;\Rightarrow\; 6 = 18 - 12\cdot 1
\end{aligned}
Now start from the gcd and substitute upward, eliminating remainders until only
48 and 18 remain:
\begin{aligned}
6 &= 18 - 12 \\
&= 18 - (48 - 18\cdot 2) \\
&= 48\cdot(-1) + 18\cdot 3.
\end{aligned}
So x = -1 and y = 3.
The forward (table) version
Back-substitution is fiddly to automate. The slicker form carries the coefficients
forward alongside the remainders. Keep a running pair
(x, y) for each remainder so that
r = 48x + 18y holds on every row, and update them with the same
quotient q that Euclid uses:
\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).
When the remainder hits 0, the previous row holds the gcd together
with its Bézout coefficients — computed in a single forward pass.
Why we care: 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. Finding
inverses quickly is exactly what makes RSA decryption, Diffie–Hellman, and a hundred other
algorithms practical.