Algoritmo de Euclides extendido: mcd e identidad de Bézout paso a paso

La idea

El máximo común divisor no cambia si al mayor de los dos números le restamos el menor, y por tanto tampoco si lo sustituimos por su resto al dividir:

$$\operatorname{mcd}(a,b)=\operatorname{mcd}(b,\,r)\qquad\text{donde } a=bq+r,\ 0\le r<b.$$

Se repite hasta que el resto sea $0$: el último resto distinto de cero es el $\operatorname{mcd}$. Aparece ya en los Elementos de Euclides.

La tabla extendida

Se escribe una tabla con columnas $q_i, r_i, s_i, t_i$, empezando por $r_0=a$ ($s_0=1$, $t_0=0$) y $r_1=b$ ($s_1=0$, $t_1=1$). En cada fila $q_i$ es el cociente de $r_{i-2}$ entre $r_{i-1}$ y

$$r_i=r_{i-2}-q_i\,r_{i-1},\qquad s_i=s_{i-2}-q_i\,s_{i-1},\qquad t_i=t_{i-2}-q_i\,t_{i-1}.$$

Siempre se cumple $r_i=s_i\,a+t_i\,b$. Al llegar a $r_i=0$, la fila anterior da el $\operatorname{mcd}$ y los coeficientes de la identidad de Bézout.

Un ejemplo completo

Calculemos $\operatorname{mcd}(252,105)$:

$q_i$	$r_i$	$s_i$	$t_i$
	$252$	$1$	$0$
	$105$	$0$	$1$
$2$	$42$	$1$	$-2$
$2$	$21$	$-2$	$5$
$2$	$0$	$5$	$-12$

El último resto no nulo es $21$, así que $\operatorname{mcd}(252,105)=21$ y

$$21=(-2)\cdot252+5\cdot105.$$

Comprobación: $-504+525=21$.

Errores típicos

• Parar un paso tarde o pronto: el $\operatorname{mcd}$ es el último resto distinto de cero, no el $0$ final.
• Equivocarse con el signo de $s_i$ y $t_i$ al restar $q_i\,s_{i-1}$: conviene comprobar siempre $s\,a+t\,b=\operatorname{mcd}$.
• Pensar que $s$ y $t$ son únicos: hay infinitas parejas; la tabla da una de ellas.
• Intercambiar $a$ y $b$ sin cambiar $s$ y $t$ de sitio.

Dónde se usa

Es la pieza de base de la aritmética modular: de ella salen los inversos modulares (y con ellos la clave privada de RSA), las congruencias lineales y el teorema chino del resto.