Usando el algoritmo de Euclides extendido.
Encontrar los coeficientes de Bézout es el proceso para calcular los enteros $x$ y $y$ tales que $ax + by = \gcd(a, b)$ para ciertos enteros $a$ y $b$. A esta ecuación la conocemos como la Identidad de Bézout. Aunque la identidad garantiza que esos enteros existen, el cálculo real normalmente lo haces usando el Algoritmo de Euclides Extendido. Este método funciona aplicando el algoritmo de Euclides estándar para encontrar el máximo común divisor (MCD) y luego regresando los pasos para escribir el MCD como una combinación lineal de los valores iniciales.
Esta técnica es una pieza fundamental de la teoría de números y es esencial para resolver ecuaciones diofánticas lineales de la forma $ax + by = c$. Si $c$ es un múltiplo de $\gcd(a, b)$, la ecuación tiene soluciones enteras; si no, no tiene ninguna. Además, encontrar los coeficientes de Bézout es la forma estándar de calcular inversos multiplicativos modulares. Para encontrar el inverso de $a$ módulo $m$ (donde $\gcd(a, m) = 1$), solo tienes que resolver $ax + my = 1$; la $x$ que obtengas cumple que $ax \equiv 1 \pmod m$.
La idea detrás del proceso es que cada residuo que sale en el algoritmo de Euclides es una combinación lineal de los dos residuos anteriores. Como el algoritmo empieza con $a$ y $b$ (que son combinaciones lineales obvias de sí mismos), y el MCD es simplemente el último residuo que no es cero, puedes demostrar por inducción que el MCD se puede escribir como una combinación lineal entera de $a$ y $b$.
Identidad de Bézout Para cualquier par de enteros $a$ y $b$ (que no sean ambos cero), si $d = \gcd(a, b)$, entonces existen enteros $x$ y $y$ tales que: $$ax + by = d$$
Solución general para ecuaciones diofánticas lineales Si $(x_0, y_0)$ es una solución particular de $ax + by = d$, entonces todas las soluciones enteras $(x, y)$ se ven así: $$x = x_0 + \frac{b}{d}k, \quad y = y_0 - \frac{a}{d}k \quad \text{para } k \in \mathbb{Z}$$
Recurrencia del Algoritmo de Euclides Extendido Para calcular los coeficientes de forma sistemática sin tener que hacer la sustitución hacia atrás a mano, puedes definir las sucesiones $x_i$ y $y_i$ junto con los residuos $r_i$ del algoritmo de Euclides. Toma $r_0 = a, r_1 = b$. Toma $x_0 = 1, x_1 = 0$. Toma $y_0 = 0, y_1 = 1$.
Para $i \geq 1$, si $r_{i+1} = r_{i-1} - q_i r_i$ (donde $q_i$ es el cociente), los coeficientes los actualizas así: $$x_{i+1} = x_{i-1} - q_i x_i$$ $$y_{i+1} = y_{i-1} - q_i y_i$$ Esto mantiene la propiedad $r_i = a x_i + b y_i$ en cada paso.
Aquí te muestro que para cualquier $a, b \in \mathbb{Z}$, puedes expresar el $\gcd(a, b)$ como una combinación lineal $ax + by$. Para esto, usa la estructura del Algoritmo de Euclides.
Paso 1: El Algoritmo de Euclides Toma $r_0 = a$ y $r_1 = b$. Haz divisiones sucesivas: $$ \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_{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} $$ Aquí, $r_n$ es el último residuo que no es cero, así que $r_n = \gcd(a, b)$.
Paso 2: Argumento inductivo La idea es que cada residuo $r_k$ en esta secuencia lo puedes escribir de la forma $r_k = a s_k + b t_k$ para algunos enteros $s_k, t_k$. Usa inducción fuerte sobre $k$.
Casos base: Para $k=0$: $r_0 = a = a(1) + b(0)$. Entonces, $s_0=1, t_0=0$. Para $k=1$: $r_1 = b = a(0) + b(1)$. Entonces, $s_1=0, t_1=1$.
Paso inductivo: Supón que para todo $j < k$ (donde $k \ge 2$), puedes escribir $r_j = a s_j + b t_j$ para ciertos enteros $s_j, t_j$. Del paso del algoritmo de división que define a $r_k$, tienes: $$r_{k-2} = q_{k-1} r_{k-1} + r_k$$ Si despejas $r_k$: $$r_k = r_{k-2} - q_{k-1} r_{k-1}$$ Usando la hipótesis inductiva, sustituye las combinaciones lineales de $r_{k-2}$ y $r_{k-1}$: $$r_k = (a s_{k-2} + b t_{k-2}) - q_{k-1} (a s_{k-1} + b t_{k-1})$$ Agrupa los términos de $a$ y $b$: $$r_k = a (s_{k-2} - q_{k-1} s_{k-1}) + b (t_{k-2} - q_{k-1} t_{k-1})$$ Como los términos $s$, los términos $t$ y los términos $q$ son todos enteros, lo que está adentro de los paréntesis también son enteros. Define $s_k = s_{k-2} - q_{k-1} s_{k-1}$ y $t_k = t_{k-2} - q_{k-1} t_{k-1}$. Así, $r_k = a s_k + b t_k$.
Conclusión: Como esta propiedad se cumple para todos los residuos que genera el algoritmo, también se debe cumplir para el último residuo que no es cero, $r_n$. Por lo tanto, existen enteros $x = s_n$ y $y = t_n$ tales que: $$r_n = \gcd(a, b) = ax + by$$