Bézout's identity and the extended Euclidean algorithm

Why this matters

Bézout's identity says that for any two integers $a, b$, there exist integers $s, t$ with $as + bt = \gcd(a, b)$. That sentence has more cryptographic consequences than almost anything else in this course: it's how you compute modular inverses (set $\gcd(a, n) = 1$, then $s$ is $a^{-1} \bmod n$), how you solve linear Diophantine equations, how RSA recovers the private exponent $d$ from $e$ and $\varphi(n)$, and how the Chinese remainder theorem stitches residues together. The extended Euclidean algorithm is the constructive proof — it doesn't just show $s, t$ exist, it produces them in the same number of steps as plain gcd. Building this is the project for the module, so spend time here.

Demo

Bézout's identity: for any $a, b \in \mathbb{Z}$ (not both zero) there exist $s, t \in \mathbb{Z}$ with $as + bt = \gcd(a, b)$. The extended Euclidean algorithm computes alongside the gcd by maintaining the invariant for the running remainder at each step. Concretely, if at step we have , then .

Try it yourself

1. Run xgcd(1071, 462) and verify by direct multiplication that $1071 s + 462 t = 21$. Then compute by hand on paper — back-substitute through the Euclidean steps from the previous task.
2. Compute xgcd(240, 46). You should get $g = 2$, with some $s, t$ satisfying $240 s + 46 t = 2$. Verify the equation holds.

Prompt your AI

Use these three in order. Each builds on the one before.

1. Basics & terminology

In one paragraph, state Bézout's identity in plain English and give a concrete example with small numbers (say $a=12, b=8$). Why is it surprising that you can always write the gcd as an integer combination of $a$ and $b$?

2. Why it works (the mechanism)

Walk me through how the extended Euclidean algorithm maintains the invariant $a s_i + b t_i = r_i$ at every step. Start from $(s_0, t_0, r_0) = (1, 0, a)$ and $(s_1, t_1, r_1) = (0, 1, b)$, and show how the update rule preserves it.

3. Advanced — application & what's next

Given that Bézout's identity gives us $a s + b t = 1$ when $\gcd(a, b) = 1$, derive the formula for $a^{-1} \bmod b$ from it. Then explain how RSA's key generation uses this exact computation to derive the private exponent $d$ from the public exponent $e$ and $\varphi(n)$.

References

• Wikipedia — Bézout's identity
• Wikipedia — Extended Euclidean algorithm
• Ireland & Rosen — A Classical Introduction to Modern Number Theory (Springer)