mcd(a,b) = ax + by.
El concepto de expresar el máximo común divisor (MCD) como una combinación lineal está resumido formalmente en la Identidad de Bézout. Este teorema dice que para cualesquiera dos enteros $a$ y $b$ (que no sean ambos cero), su máximo común divisor $d = \gcd(a,b)$ se puede escribir de la forma $ax + by = d$ para algunos enteros $x$ e $y$. A estos enteros $x$ e $y$ se les llama frecuentemente coeficientes de Bézout. Aunque normalmente defines el MCD por sus propiedades multiplicativas (es el entero más grande que divide a ambos números), esta identidad revela una propiedad aditiva muy profunda: el MCD es el entero positivo más pequeño que puedes formar sumando y restando múltiplos de $a$ y $b$.
Este concepto 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$. La identidad garantiza que una ecuación así tiene soluciones enteras si y solo si $c$ es un múltiplo de $\gcd(a,b)$. Además, este principio es la base teórica del Algoritmo de Euclides Extendido, que te da un método constructivo para encontrar los coeficientes $x$ e $y$.
En las olimpiadas de matemáticas, esta técnica se usa seguido para demostrar que dos números son primos relativos y para encontrar inversos modulares. Por ejemplo, si $\gcd(a, m) = 1$, la Identidad de Bézout implica que existen enteros $x, y$ tales que $ax + my = 1$. Si tomas esta ecuación módulo $m$, obtienes $ax \equiv 1 \pmod{m}$, lo que demuestra que $x$ es el inverso modular de $a$. Este puente entre las combinaciones lineales y la aritmética modular es una herramienta poderosa para simplificar problemas complejos de divisibilidad.
Identidad de Bézout Para cualesquiera enteros $a$ y $b$, no ambos cero, sea $d = \gcd(a,b)$. Existen enteros $x$ e $y$ tales que: $$ax + by = d$$
Combinaciones Lineales Generales El conjunto de todas las combinaciones lineales posibles de $a$ y $b$ es exactamente el conjunto de los múltiplos de su MCD. Un entero $c$ se puede escribir como $ax + by = c$ si y solo si: $$c \equiv 0 \pmod{\gcd(a,b)}$$
Condición de Primos Relativos Dos enteros $a$ y $b$ son primos entre sí (primos relativos) si y solo si existen enteros $x$ e $y$ tales que: $$ax + by = 1$$
Estructura de los Coeficientes Si $(x_0, y_0)$ es una solución de $ax + by = d$, entonces hay infinitas soluciones dadas por: $$x = x_0 + \frac{k b}{d}, \quad y = y_0 - \frac{k a}{d} \quad \text{para cualquier } k \in \mathbb{Z}$$
Teorema: Sean $a$ y $b$ enteros, no ambos cero. Sea $S$ el conjunto de todas las combinaciones lineales positivas de $a$ y $b$: $$S = {ax + by \mid x, y \in \mathbb{Z}, ax + by > 0}$$ Entonces $S$ contiene un elemento mínimo $d$, y $d = \gcd(a,b)$.
Demostración:
Existencia de un elemento mínimo: Primero, hay que ver que $S$ no es vacío. Como $a \neq 0$ o $b \neq 0$, puedes elegir $x, y$ tales que $ax+by > 0$ (por ejemplo, si $a > 0$, toma $x=1, y=0$; si $a < 0$, toma $x=-1, y=0$). Por el Principio del Buen Orden, todo conjunto no vacío de enteros positivos debe tener un elemento mínimo. Sea $d$ el elemento más pequeño de $S$. Por definición, $d = ax_0 + by_0$ para algunos enteros $x_0, y_0$.
Prueba de que $d$ divide a $a$ y a $b$: Usa el Algoritmo de la División para dividir $a$ entre $d$. Existen enteros $q$ y $r$ tales que: $$a = dq + r, \quad \text{donde } 0 \le r < d$$ Si sustituyes la expresión de $d$: $$r = a - dq = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0)$$ Así, $r$ es una combinación lineal de $a$ y $b$. Si $r > 0$, entonces $r \in S$. Sin embargo, $r < d$, y $d$ es el elemento más pequeño de $S$. Esto es una contradicción. Por lo tanto, $r$ tiene que ser $0$, lo que implica que $d \mid a$. Con un argumento similar, ves que $d \mid b$. Así que $d$ es un divisor común de $a$ y $b$.
Prueba de que $d$ es el máximo común divisor: Toma cualquier divisor común arbitrario $c$ de $a$ y $b$. Entonces $a = ck$ y $b = cm$ para algunos enteros $k, m$. Al sustituir esto en la expresión de $d$: $$d = ax_0 + by_0 = (ck)x_0 + (cm)y_0 = c(kx_0 + my_0)$$ Como $d > 0$ y $kx_0 + my_0$ es un entero, $c$ debe dividir a $d$, lo que implica que $c \le d$.
Como $d$ es un divisor común y cualquier otro divisor común $c$ es menor o igual a $d$, entonces $d$ es el máximo común divisor.
$$\square$$