Existencia de Soluciones

Teoría

El estudio de las Ecuaciones Diofánticas Lineales se enfoca en encontrar soluciones enteras $(x, y)$ para ecuaciones de la forma $ax + by = c$, donde $a, b,$ y $c$ son enteros dados. La pregunta más básica en este tema es determinar si de plano existen soluciones enteras. A diferencia de las ecuaciones algebraicas normales con números reales, que casi siempre tienen soluciones si los coeficientes no son cero, las ecuaciones diofánticas son más exigentes porque las variables tienen que ser enteros. La existencia de soluciones depende totalmente del máximo común divisor (MCD) de los coeficientes $a$ y $b$.

Este concepto se basa mucho en las propiedades de la divisibilidad. Por pura intuición, cualquier combinación lineal de dos enteros $a$ y $b$ tiene que compartir los divisores comunes de $a$ y $b$. Específicamente, si un número $d$ divide tanto a $a$ como a $b$, también tiene que dividir a cualquier expresión entera $ax + by$. Por lo tanto, para que la ecuación se cumpla, la constante $c$ tiene que ser divisible entre $\gcd(a,b)$. Si $c$ no es un múltiplo de este MCD, la "cuadrícula" de valores posibles que genera $ax + by$ simplemente nunca va a caer en $c$, lo que hace que la ecuación no tenga solución en los enteros.

Este criterio es tanto necesario como suficiente, así que es un primer paso súper útil para resolver problemas diofánticos en competencias como el AMC 12 y el AIME. Antes de que intentes usar el Algoritmo de Euclides Extendido o aritmética modular para hallar valores específicos de $x$ y $y$, tienes que verificar esta condición de existencia. Este teorema es una extensión directa de la Identidad de Bézout, que dice que la ecuación $ax + by = \gcd(a,b)$ siempre tiene soluciones enteras.

Fórmulas Clave

Ecuación Diofántica Lineal Estándar $$ax + by = c$$ donde $a, b, c \in \mathbb{Z}$ y buscas soluciones $x, y \in \mathbb{Z}$.

El Teorema de Existencia Sea $d = \gcd(a, b)$. La ecuación $ax + by = c$ tiene soluciones enteras si y solo si $d$ divide a $c$: $$\exists x, y \in \mathbb{Z} \text{ tal que } ax + by = c \iff \gcd(a, b) \mid c$$

Identidad de Bézout Para cualesquiera enteros $a$ y $b$ que no sean cero, sea $d = \gcd(a,b)$. Existen enteros $x_0$ y $y_0$ tales que: $$ax_0 + by_0 = d$$

Condición para que no haya soluciones Si $\gcd(a, b) \nmid c$, entonces el conjunto de soluciones está vacío: $$(x, y) \in \emptyset$$

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 prueba tiene dos partes: mostrar que la condición es necesaria ($\implies$) y mostrar que es suficiente ($\impliedby$).

Parte 1: Necesidad ($\implies$) Supón que la ecuación tiene soluciones enteras. Sea $(x, y)$ un par de enteros que cumple $ax + by = c$. Por la definición del máximo común divisor, $d = \gcd(a, b)$ implica que $d \mid a$ y $d \mid b$. Por lo tanto, puedes escribir $a = dm$ y $b = dn$ para algunos enteros $m, n$. Si los sustituyes en la ecuación: $$ (dm)x + (dn)y = c $$ $$ d(mx + ny) = c $$ Como $x, y, m,$ y $n$ son todos enteros, la expresión $(mx + ny)$ es un entero. Ponle $k = mx + ny$. Así que $c = dk$. Por definición, esto significa que $d$ divide a $c$ ($d \mid c$). Esto demuestra que si existe una solución, $c$ tiene que ser un múltiplo de $\gcd(a, b)$.

Parte 2: Suficiencia ($\impliedby$) Ahora supón que $d \mid c$. Lo que hay que mostrar es que existen enteros $x$ y $y$ que cumplen $ax + by = c$. Como $d \mid c$, existe un entero $k$ tal que $c = kd$.

Según la Identidad de Bézout, como $d = \gcd(a, b)$, existen enteros $x_0$ y $y_0$ tales que: $$ ax_0 + by_0 = d $$ Para obtener el valor de $c$, multiplica toda la ecuación por el entero $k$: $$ k(ax_0 + by_0) = k(d) $$ $$ a(kx_0) + b(ky_0) = kd $$ Como $c = kd$, tienes: $$ a(kx_0) + b(ky_0) = c $$ Toma $x = kx_0$ y $y = ky_0$. Como $k, x_0,$ y $y_0$ son enteros, entonces $x$ y $y$ son enteros. Así, ya encontraste un par de enteros $(x, y)$ que cumple la ecuación.

Conclusión Ya quedó demostrado que las soluciones existen si y solo si $\gcd(a, b)$ divide a $c$. $\square$