Condición de Divisibilidad del MCD

Teoría

La Condición de Divisibilidad del MCD es el criterio fundamental que usas para determinar si una ecuación diofántica lineal tiene solución. Una ecuación diofántica lineal es una ecuación de la forma $ax + by = c$, donde $a, b,$ y $c$ son enteros dados, y buscas soluciones enteras para $x$ y $y$. La condición dice que esta ecuación tiene soluciones enteras si y solo si el máximo común divisor de $a$ y $b$ divide a $c$. Si $\gcd(a, b)$ no divide a $c$, no existen soluciones enteras.

Este concepto es crucial en teoría de números y matemáticas de competencia porque te da una "prueba de existencia" inmediata antes de que intentes buscar soluciones específicas. Se basa en la estructura de los enteros: cualquier combinación lineal de dos números $a$ y $b$ tiene que ser un múltiplo de su máximo común divisor. Esto está muy relacionado con la Identidad de Bézout, que asegura que la ecuación $ax + by = \gcd(a, b)$ siempre tiene soluciones enteras.

Intuitivamente, puedes visualizar el conjunto de todos los valores generados por $ax + by$ como una rejilla en la recta numérica. El "tamaño del paso" o el hueco positivo más pequeño entre estos valores es $d = \gcd(a, b)$. Por lo tanto, la combinación lineal $ax + by$ solo puede generar múltiplos de $d$. Si el número objetivo $c$ cae entre estos múltiplos (o sea, si $c$ no es divisible entre $d$), es imposible llegar a $c$ usando pasos enteros de tamaño $a$ y $b$.

Fórmulas Clave

El Teorema de Existencia La ecuación diofántica lineal $ax + by = c$ tiene soluciones enteras $(x, y)$ si y solo si: $$ \gcd(a, b) \mid c $$ donde $a, b, c \in \mathbb{Z}$ y $a$ y $b$ no son cero al mismo tiempo.

Identidad de Bézout Un caso específico e importante es cuando $c = \gcd(a, b)$. Siempre existen enteros $x$ y $y$ tales que: $$ ax + by = \gcd(a, b) $$

Estructura de la Solución General Si se cumple la condición $\gcd(a, b) \mid c$ y encuentras una solución particular $(x_0, y_0)$, todas las soluciones enteras están dadas por: $$ x = x_0 + \frac{b}{d}k, \quad y = y_0 - \frac{a}{d}k $$ donde $d = \gcd(a, b)$ y $k$ es cualquier entero.

Demostración

Teorema: La ecuación diofántica lineal $ax + by = c$ tiene soluciones enteras si y solo si $d \mid c$, donde $d = \gcd(a, b)$.

Demostración: La demostración consiste en dos partes: mostrar la necesidad ($\implies$) y la suficiencia ($\Longleftarrow$).

Parte 1: Necesidad ($\implies$) Supón que la ecuación $ax + by = c$ tiene soluciones enteras. Toma a $(x_0, y_0)$ como una de esas soluciones.

1. Por la definición del máximo común divisor, $d = \gcd(a, b)$ divide tanto a $a$ como a $b$.
2. Puedes escribir $a = dm$ y $b = dn$ para algunos enteros $m, n$.
3. Si sustituyes esto en la ecuación: $$ (dm)x_0 + (dn)y_0 = c $$ $$ d(mx_0 + ny_0) = c $$
4. Como $x_0, y_0, m,$ y $n$ son enteros, la cantidad $(mx_0 + ny_0)$ también es un entero.
5. Por lo tanto, $c$ es un múltiplo de $d$, lo que significa que $d \mid c$.

Parte 2: Suficiencia ($\Longleftarrow$) Supón que $d \mid c$. Lo que hay que mostrar es que existen enteros $x$ y $y$ que cumplen $ax + by = c$.

1. Por la Identidad de Bézout, existen enteros $u$ y $v$ tales que: $$ au + bv = d $$
2. Como supusiste que $d \mid c$, existe un entero $k$ tal que $c = kd$.
3. Multiplica la ecuación de Bézout por $k$: $$ k(au + bv) = k(d) $$ $$ a(ku) + b(kv) = kd $$
4. Sustituye $c$ en lugar de $kd$: $$ a(ku) + b(kv) = c $$
5. Si tomas $x = ku$ y $y = kv$, como $k, u,$ y $v$ son enteros, entonces $x$ y $y$ también son enteros.
6. Así, ya encontraste soluciones enteras para la ecuación.

Conclusión: La ecuación $ax + by = c$ se puede resolver en los enteros si y solo si $\gcd(a, b)$ divide a $c$. $\square$