Bézout's Identity and the Extended Euclidean Algorithm

The Euclidean algorithm finds $\gcd(a, b)$. Kept track of carefully, it gives more: a way to build the gcd out of $a$ and $b$. This is the tool behind modular inverses, linear congruences and RSA, so it is worth getting fluent.

Bézout's identity. If $a$ and $b$ are integers, not both $0$, then there are integers $x$ and $y$ with $$ax + by = \gcd(a, b).$$ Moreover, $\gcd(a, b)$ is the smallest positive number of the form $ax + by$. Finding $x$ and $y$ is called the extended Euclidean algorithm.

Por qué funciona

Each remainder in the Euclidean algorithm is a combination of $a$ and $b$. The first is $r_1 = a - q_1 b$. The next is $r_2 = b - q_2 r_1$, and since $r_1$ is a combination, so is $r_2$. Every later remainder is "older remainder minus a multiple of the one after it," so by induction every remainder, including the last nonzero one, the gcd, is a combination $ax + by$. And no smaller positive combination exists: the gcd divides $a$ and $b$, so it divides every $ax + by$.

Ejemplo resuelto: Back-substitution

Find integers $x$ and $y$ with $252x + 198y = 18$.

Run the algorithm and solve each line for its remainder: $54 = 252 - 1 \cdot 198$, $\ 36 = 198 - 3 \cdot 54$, $\ 18 = 54 - 1 \cdot 36$.
Start from the line with the gcd: $18 = 54 - 36$.
Replace $36$: $18 = 54 - (198 - 3 \cdot 54) = 4 \cdot 54 - 198$.
Replace $54$: $18 = 4(252 - 198) - 198 = 4 \cdot 252 - 5 \cdot 198$.
Check: $4 \cdot 252 - 5 \cdot 198 = 1008 - 990 = 18$.

Respuesta: $x = 4$, $y = -5$.

The same computation as a table: each remainder is written as $252s + 198t$, using the two rows above it. Every row checks itself, and the row of the gcd gives $x$ and $y$.

Ejemplo resuelto: Bigger numbers

Write $\gcd(2431, 1001)$ as a combination of $2431$ and $1001$.

$2431 = 1001 \cdot 2 + 429$ and $1001 = 429 \cdot 2 + 143$, then $429 = 143 \cdot 3$. So the gcd is $143$.
$143 = 1001 - 2 \cdot 429$.
$429 = 2431 - 2 \cdot 1001$, so $143 = 1001 - 2(2431 - 2 \cdot 1001) = 5 \cdot 1001 - 2 \cdot 2431$.
Check: $5 \cdot 1001 - 2 \cdot 2431 = 5005 - 4862 = 143$.

Respuesta: $143 = 2431 \cdot (-2) + 1001 \cdot 5$.

Ejemplo resuelto: Choosing a solution in a range

Find $x$ and $y$ with $47x + 15y = 1$ and $0 \le x < 15$.

$47 = 15 \cdot 3 + 2$ and $15 = 2 \cdot 7 + 1$.
$1 = 15 - 7 \cdot 2 = 15 - 7(47 - 3 \cdot 15) = 22 \cdot 15 - 7 \cdot 47$. So $x = -7$, $y = 22$ works.
Adding $15$ to $x$ and subtracting $47$ from $y$ keeps $47x + 15y$ the same (it adds $47 \cdot 15 - 15 \cdot 47 = 0$). So $x = 8$, $y = -25$.
Check: $47 \cdot 8 - 15 \cdot 25 = 376 - 375 = 1$.

Respuesta: $x = 8$, $y = -25$.

Error común

Losing a sign during substitution. Expanding $4(252 - 198) - 198$ as $4 \cdot 252 - 4 \cdot 198 + 198$ gives the wrong $y$. Always finish by multiplying out $ax + by$: if it does not equal the gcd, something slipped. Also remember the answer is not unique: $x = 4 + 11t$, $y = -5 - 14t$ works for every integer $t$ (try $t = 1$: $252 \cdot 15 - 198 \cdot 19 = 18$).

Idea clave

Work the Euclidean algorithm backward (or keep a running table) to write $\gcd(a, b) = ax + by$. Then check by multiplying out.

Práctica

Se apoya en

Lleva a

Fuentes y lecturas