ax + by = c tiene soluciones enteras si y solo si el mcd(a,b) divide a c.
Una Ecuación Diofántica Lineal es una ecuación algebraica de la forma $ax + by = c$, donde $a, b$ y $c$ son enteros que ya conoces, y lo que buscas son soluciones enteras para $x$ y $y$. A diferencia de las ecuaciones lineales normales en los números reales, que representan una línea continua, las ecuaciones diofánticas limitan el dominio al conjunto de los números enteros $\mathbb{Z}$. Geométricamente, resolver esta ecuación es lo mismo que encontrar todos los puntos de la cuadrícula (puntos con coordenadas enteras) que están sobre la línea que define la ecuación.
Este concepto es fundamental en la teoría de números y en las matemáticas de competencia porque junta el álgebra simple con las propiedades de divisibilidad. Que la ecuación tenga solución depende totalmente del máximo común divisor (MCD) de los coeficientes $a$ y $b$. Específicamente, la ecuación tiene soluciones enteras si y solo si $\gcd(a, b)$ divide a $c$. Este resultado sale directo de la Identidad de Bézout.
En cuanto encuentras una sola solución particular $(x_0, y_0)$ —que usualmente sacas con el Algoritmo de Euclides Extendido o aritmética modular— existen infinitas soluciones. Estas soluciones siguen un patrón periódico que depende de la pendiente de la línea, $-\frac{a}{b}$. En competencias como el AMC 12 o el AIME, vas a ver estas ecuaciones seguido en problemas de razonamiento que usan combinaciones de objetos discretos (como monedas o estampillas) o como pasos intermedios para resolver congruencias modulares más difíciles.
1. Existencia de Soluciones La ecuación $ax + by = c$ tiene soluciones enteras si y solo si: $$ \gcd(a, b) \mid c $$ Si tomas $d = \gcd(a, b)$ y resulta que $d \nmid c$, entonces no hay soluciones enteras.
2. Solución General Si ya tienes una solución particular $(x_0, y_0)$, el conjunto de todas las soluciones enteras $(x, y)$ se ve así: $$ x = x_0 + \frac{b}{d}k $$ $$ y = y_0 - \frac{a}{d}k $$ donde $k$ es cualquier entero ($k \in \mathbb{Z}$). Fíjate que los signos son opuestos; mientras $x$ aumenta, $y$ tiene que disminuir para que se mantenga la igualdad.
3. Problema de las Monedas de Frobenius (Teorema de Chicken McNugget) Para enteros positivos coprimos $a$ y $b$ (donde $\gcd(a, b) = 1$), el entero más grande $c$ que no puedes escribir de la forma $ax + by = c$ usando enteros no negativos $x, y$ es: $$ g(a,b) = ab - a - b $$
Teorema: La ecuación $ax + by = c$ tiene soluciones enteras si y solo si $d \mid c$ (donde $d = \gcd(a, b)$). Además, si $(x_0, y_0)$ es una solución particular, todas las soluciones tienen la forma $x = x_0 + \frac{b}{d}k$ y $y = y_0 - \frac{a}{d}k$.
Demostración de la Existencia:
$(\Rightarrow)$ Supón que existen enteros $x$ y $y$ tales que $ax + by = c$. Como $d = \gcd(a, b)$, por definición $d \mid a$ y $d \mid b$. Así que $a = dm$ y $b = dn$ para algunos enteros $m, n$. Si sustituyes esto en la ecuación: $$ dmx + dny = c \implies d(mx + ny) = c $$ Como $mx + ny$ es un entero, $d$ tiene que dividir a $c$. Por eso, $d \mid c$ es una condición necesaria.
$(\Leftarrow)$ Ahora supón que $d \mid c$. Por la Identidad de Bézout, existen enteros $x'$ y $y'$ tales que $ax' + by' = d$. Como $d \mid c$, puedes escribir $c = kd$ para algún entero $k$. Si multiplicas la ecuación de Bézout por $k$: $$ k(ax' + by') = kd \implies a(kx') + b(ky') = c $$ Si tomas $x_0 = kx'$ y $y_0 = ky'$, entonces $(x_0, y_0)$ es una solución entera válida.
Demostración de la Solución General:
Toma $(x_0, y_0)$ como una solución particular tal que $ax_0 + by_0 = c$. Imagina que $(x, y)$ es cualquier otra solución entera tal que $ax + by = c$. Si restas la primera ecuación a la segunda: $$ (ax + by) - (ax_0 + by_0) = c - c $$ $$ a(x - x_0) + b(y - y_0) = 0 $$ $$ a(x - x_0) = -b(y - y_0) $$ Divide ambos lados entre $d = \gcd(a, b)$: $$ \frac{a}{d}(x - x_0) = -\frac{b}{d}(y - y_0) $$ Digamos que $A = \frac{a}{d}$ y $B = \frac{b}{d}$. Nota que $\gcd(A, B) = 1$ porque dividiste entre el factor común. La ecuación queda así: $$ A(x - x_0) = -B(y - y_0) $$ Como $B$ divide al lado derecho, $B$ también tiene que dividir al lado izquierdo: $B \mid A(x - x_0)$. Como $\gcd(A, B) = 1$, por el Lema de Euclides, $B$ tiene que dividir a $(x - x_0)$. Por eso, puedes escribir: $$ x - x_0 = B k \implies x = x_0 + \frac{b}{d}k $$ para algún entero $k$. Si sustituyes esto de nuevo en $A(x - x_0) = -B(y - y_0)$: $$ A(Bk) = -B(y - y_0) $$ $$ Ak = -(y - y_0) \implies y = y_0 - Ak \implies y = y_0 - \frac{a}{d}k $$ Así que cualquier solución tiene que verse de esta forma. Por el otro lado, si sustituyes estos valores vas a ver que cualquier par de esta forma cumple con la ecuación original. $\square$