Extended Euclidean algorithm

How it works

Euclid’s algorithm finds $g = \gcd(a, b)$ by repeated division. Its extended form also finds integers $s$ and $t$ with $s \cdot a + t \cdot b = g$, Bézout’s identity. For $240$ and $46$: $\gcd = 2 = -9 \cdot 240 + 47 \cdot 46$.

There are two ways to get them. The table carries two extra columns along with the remainders, so that every row satisfies $r_i = s_i a + t_i b$; each new row is the row two above minus the quotient times the row above. Back-substitution goes the other way: it starts from the last division, which expresses $g$ through the two previous remainders, and replaces remainders by their own divisions until only $a$ and $b$ are left. Both give the same pair.

The pair is not unique: $(s + k b / g,\ t - k a / g)$ works for every integer $k$. When $g = 1$, reducing the identity modulo $b$ gives $s \cdot a \equiv 1$, so $s$ is the inverse of $a$ modulo $b$. This is how RSA computes its private exponent, and it is the core of solving linear congruences and the Chinese remainder theorem.