Usando la Identidad de Bézout

Teoría

La Identidad de Bézout es un teorema fundamental en la teoría de números elemental que conecta el máximo común divisor (MCD) de dos enteros con sus combinaciones lineales. Específicamente, dice que para cualquier par de enteros $a$ y $b$ que no sean cero, si $d = \gcd(a,b)$, entonces existen enteros $x$ e $y$ tales que $ax + by = d$. Además, $d$ es el entero positivo más pequeño que puedes escribir de la forma $ax + by$.

Esta identidad es la base para resolver ecuaciones diofánticas lineales de la forma $ax + by = c$. Te da la condición necesaria y suficiente para que existan soluciones enteras: la ecuación tiene soluciones si y solo si $\gcd(a,b)$ divide a $c$. Si esta condición se cumple, la Identidad de Bézout te permite encontrar una solución particular, normalmente usando el Algoritmo de Euclides Extendido, que luego puedes usar para generar el conjunto infinito de soluciones generales.

Intuitivamente, la Identidad de Bézout te dice cómo es la estructura de los números generados por $a$ y $b$. El conjunto de todas las combinaciones lineales enteras de $a$ y $b$ forma un ideal en el anillo de los enteros, y este ideal consiste exactamente en los múltiplos de su MCD. Este concepto es crucial en las matemáticas de competencia, no solo para resolver ecuaciones, sino también para demostrar propiedades sobre inversos modulares (que existen si y solo si $\gcd(a,n)=1$) y para establecer el Lema de Euclides.

Fórmulas Clave

Identidad de Bézout Para cualesquiera enteros $a$ y $b$ (que no sean ambos cero), sea $d = \gcd(a,b)$. Existen enteros $x$ e $y$ tales que: $$ax + by = d$$

Existencia de Soluciones para Ecuaciones Diofánticas Lineales La ecuación diofántica lineal $ax + by = c$ tiene soluciones enteras para $x$ e $y$ si y solo si: $$\gcd(a,b) \mid c$$

Caso de Coprimos Si $a$ y $b$ son primos relativos (coprimos), entonces $\gcd(a,b) = 1$. Por lo tanto, existen enteros $x$ e $y$ tales que: $$ax + by = 1$$ Esto implica que $ax \equiv 1 \pmod{b}$, lo que significa que $x$ es el inverso multiplicativo modular de $a$ módulo $b$.

Conjunto de Combinaciones Lineales El conjunto de todas las combinaciones lineales de $a$ y $b$ es exactamente el conjunto de los múltiplos de su MCD: $${ax + by \mid x, y \in \mathbb{Z}} = {k \cdot \gcd(a,b) \mid k \in \mathbb{Z}}$$

Demostración

Teorema: Sean $a$ y $b$ 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}$$ Sea $d$ el elemento más pequeño en $S$. Entonces $d = \gcd(a,b)$.

Demostración:

1. 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, cualquier conjunto no vacío de enteros positivos tiene un elemento mínimo. Así que toma a $d$ como el elemento más pequeño de $S$. Por definición, $d = ax_0 + by_0$ para algunos