mcd(a,b) = ax + by para algunos enteros x, y.
La Identidad de Bézout es un teorema fundamental en la teoría de números elemental que establece una relación lineal entre dos enteros y su máximo común divisor (MCD). Específicamente, dice que para cualquier par de enteros $a$ y $b$ que no sean cero, el máximo común divisor $d = \gcd(a,b)$ lo puedes expresar como una combinación lineal entera de $a$ y $b$. En otras palabras, vas a encontrar que existen enteros $x$ y $y$ (llamados coeficientes de Bézout) tales que $ax + by = d$. Además, $d$ es el entero positivo más pequeño que puedes escribir de esta forma.
Esta identidad es clave para resolver ecuaciones diofánticas lineales de la forma $ax + by = c$. Te da la condición necesaria y suficiente para que existan soluciones: la ecuación tiene solución si y solo si $c$ es un múltiplo de $\gcd(a,b)$. En la práctica, los coeficientes $x$ y $y$ no son únicos, y puedes encontrar pares específicos usando el Algoritmo de Euclides Extendido. Esta conexión algorítmica une el teorema de existencia abstracta con un método computacional, lo que lo convierte en una herramienta muy poderosa en las matemáticas de competencia.
Intuitivamente, la Identidad de Bézout describe la "granularidad" de la retícula generada por $a$ y $b$. Si te imaginas moviéndote a lo largo de una recta numérica con pasos de tamaño $a$ y $b$ (hacia adelante o hacia atrás), el conjunto de todos los puntos a los que puedes llegar corresponde a los múltiplos de su MCD. Este concepto es la base de muchos otros resultados críticos, incluyendo el Lema de Euclides (si un primo divide a un producto, tiene que dividir a uno de los factores) y el Teorema Fundamental de la Aritmética (la factorización prima única).
La Identidad Para cualquier par de enteros $a$ y $b$, que no sean ambos cero, toma $d = \gcd(a,b)$. Existen enteros $x$ y $y$ tales que: $$ax + by = d$$
Combinaciones Lineales Generales El conjunto de todas las combinaciones lineales enteras de $a$ y $b$ es exactamente el conjunto de los múltiplos de $\gcd(a,b)$. Es decir: $${ax + by \mid x, y \in \mathbb{Z}} = {kd \mid k \in \mathbb{Z}}$$
Solubilidad de Ecuaciones Diofánticas La ecuación diofántica lineal $ax + by = c$ tiene soluciones enteras para $x$ y $y$ si y solo si: $$\gcd(a,b) \mid c$$
Condición de Primos Relativos Los enteros $a$ y $b$ son primos relativos (coprimos) si y solo si existen enteros $x$ y $y$ tales que: $$ax + by = 1$$
Teorema: Toma $a$ y $b$ como enteros, no ambos cero. Sea $S$ el conjunto de todas las combinaciones lineales enteras 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, nota que $S$ no es vacío. Incluso si $a$ o $b$ son negativos, puedes elegir $x$ y $y$ de tal forma que $ax+by > 0$ (por ejemplo, si $a \neq 0$, toma $x = a$ o $x = -a$ para obtener $a^2 > 0$). Por el Principio del Buen Orden, sabes que todo conjunto no vacío de enteros positivos tiene un elemento mínimo. Llama $d$ al elemento más pequeño en $S$. Por definición, existen enteros $x_0, y_0$ tales que: $$d = ax_0 + by_0$$
Prueba de que $d$ es un divisor común: Usa el Algoritmo de la División para dividir $a$ entre $d$. Vas a encontrar enteros $q$ y $r$ tales que $a = dq + r$, 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$, lo cual contradice la suposición de que $d$ es el elemento más pequeño de $S$. Por lo tanto, $r$ tiene que ser $0$. Esto implica que $a = dq$, así que $d \mid a$. Siguiendo un argumento similar, llegas a que $d \mid b$. Entonces, $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$. Si sustituyes 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$ es un múltiplo de $c$ y $d > 0$, se debe cumplir 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.
Por lo tanto, lo que querías mostrar es que $\gcd(a,b) = d = ax_0 + by_0$. $\square$