Encontrar x, y tales que ax + by = mcd(a,b).
El Algoritmo de Euclides Extendido es una técnica fundamental en teoría de números que extiende el Algoritmo de Euclides estándar. Mientras que el algoritmo estándar calcula el máximo común divisor (MCD) de dos enteros $a$ y $b$, la versión extendida va un paso más allá para encontrar enteros $x$ e $y$ tales que: $$ax + by = \gcd(a, b)$$ A estos enteros $x$ e $y$ se les suele llamar coeficientes de Bézout. Esta ecuación se conoce como la Identidad de Bézout, que dice que el máximo común divisor de dos números siempre se puede expresar como una combinación lineal de esos números.
Este algoritmo es súper importante para resolver ecuaciones diofánticas lineales de la forma $ax + by = c$. Existe una solución si y solo si $\gcd(a, b)$ divide a $c$. Además, el Algoritmo de Euclides Extendido es el método estándar para calcular inversos multiplicativos modulares. Si necesitas resolver $ax \equiv 1 \pmod m$, básicamente estás buscando enteros $x$ e $y$ tales que $ax + my = 1$. Esto solo es posible si $\gcd(a, m) = 1$, y el algoritmo te da el valor específico de $x$ que se requiere para criptografía (como RSA) y problemas avanzados de aritmética.
La intuición detrás del algoritmo se basa en el proceso de "sustitución hacia atrás". El algoritmo de Euclides estándar genera una secuencia de residuos, donde cada residuo es una combinación lineal de los dos anteriores. Al revertir los pasos —empezando desde el MCD (el último residuo que no es cero) y sustituyendo las expresiones de los residuos anteriores— puedes reescribir el MCD totalmente en términos de las entradas originales $a$ y $b$.
Identidad de Bézout Para cualquier par de enteros $a$ y $b$ distintos de cero, sea $d = \gcd(a, b)$. Existen enteros $x$ e $y$ tales que: $$ax + by = d$$
Solución General para Ecuaciones Diofánticas Lineales Si $(x_0, y_0)$ es una solución particular encontrada con el Algoritmo de Euclides Extendido para $ax + by = d$, entonces todas las soluciones enteras $(x, y)$ están dadas por: $$x = x_0 + k\left(\frac{b}{d}\right), \quad y = y_0 - k\left(\frac{a}{d}\right)$$ donde $k$ es cualquier entero.
Fórmula de Actualización Recursiva Cuando implementas el algoritmo (o lo haces a mano usando una tabla), si ya conoces los coeficientes $(x', y')$ para el par $(b, a \pmod b)$ tales que $b x' + (a \pmod b) y' = d$, puedes sacar los coeficientes $(x, y)$ para $(a, b)$ usando: $$x = y'$$ $$y = x' - \left\lfloor \frac{a}{b} \right\rfloor y'$$
Inverso Modular Para encontrar el inverso de $a$ módulo $m$ (que escribimos como $a^{-1}$), resuelves $ax + my = 1$. Si $\gcd(a, m) = 1$, entonces: $$a^{-1} \equiv x \pmod m$$
Teorema: Para cualquier par de enteros $a$ y $b$, existen enteros $x$ e $y$ tales que $ax + by = \gcd(a, b)$.
Demostración (por sustitución hacia atrás constructiva):
Toma $a$ y $b$ como enteros positivos con $a > b$. Aplica el Algoritmo de Euclides estándar para generar una secuencia de residuos $r_0, r_1, \dots, r_n, r_{n+1}$. Pon $r_0 = a$ y $r_1 = b$. Los pasos del algoritmo de la división son:
$$ \begin{aligned} r_0 &= q_1 r_1 + r_2 & (0 < r_2 < r_1) \ r_1 &= q_2 r_2 + r_3 & (0 < r_3 < r_2) \ &\vdots & \ r_{k-1} &= q_k r_k + r_{k+1} & (0 < r_{k+1} < r_k) \ &\vdots & \ r_{n-2} &= q_{n-1} r_{n-1} + r_n & (0 < r_n < r_{n-1}) \ r_{n-1} &= q_n r_n + 0 & \end{aligned} $$
El último residuo que no es cero, $r_n$, es el $\gcd(a, b)$.
Puedes reacomodar cada paso para expresar el residuo como una combinación lineal de los dos términos anteriores: $$r_{k+1} = r_{k-1} - q_k r_k$$
La idea es que cada residuo $r_k$ se puede expresar de la forma $r_k = s_k a + t_k b$ para algunos enteros $s_k, t_k$. Esto se puede ver por inducción o simplemente observando el proceso de sustitución hacia atrás empezando desde $r_n$.
Empieza con la ecuación para $r_n$: $$r_n = r_{n-2} - q_{n-1} r_{n-1}$$
Sustituye $r_{n-1}$ usando la relación anterior ($r_{n-1} = r_{n-3} - q_{n-2} r_{n-2}$): $$r_n = r_{n-2} - q_{n-1} (r_{n-3} - q_{n-2} r_{n-2})$$ Reacomoda los términos para agruparlos por residuos: $$r_n = (1 + q_{n-1}q_{n-2})r_{n-2} - q_{n-1}r_{n-3}$$
Continúa con este proceso, sustituyendo $r_{n-2}$, luego $r_{n-3}$, y así sucesivamente, subiendo por la cadena de ecuaciones. En cada paso, $r_n$ queda expresado como una combinación lineal de dos residuos anteriores con coeficientes enteros.
Eventualmente, llegas al principio de la cadena donde los residuos son $r_1 = b$ y $r_0 = a$. Así, llegas a una expresión: $$r_n = x a + y b$$ Como $r_n = \gcd(a, b)$, ya encontraste los enteros $x$ e $y$ tales que $ax + by = \gcd(a, b)$. $\square$