Ecuaciones lineales diofánticas

¿Qué es una ecuación diofántica?

Una ecuación diofántica es una ecuación en la que buscamos soluciones enteras (o a veces naturales). El nombre proviene de Diofanto de Alejandría, matemático griego del siglo III que estudió sistemáticamente estas ecuaciones.

La ecuación diofántica más sencilla es la lineal: $ax + by = c$, donde $a, b, c$ son enteros dados y se buscan enteros $x, y$ que la satisfagan. La pregunta fundamental es: ¿cuándo tiene solución? ¿Cómo encontrar todas las soluciones?

En los capítulos anteriores aprendimos el algoritmo de Euclides y la identidad de Bézout. Ahora usaremos esas herramientas directamente para resolver ecuaciones lineales diofánticas.

Condición de existencia: el teorema de Bézout

Sea $d = \gcd(a, b)$. La ecuación $ax + by = c$ tiene solución entera si y solo si $d \mid c$.

Demostración. Si $(x_0, y_0)$ es solución, entonces $c = ax_0 + by_0$. Como $d \mid a$ y $d \mid b$, se tiene $d \mid c$. Recíprocamente, si $d \mid c$, escribimos $c = d \cdot k$. Por Bézout existe $(u, v)$ tal que $au + bv = d$. Entonces $a(ku) + b(kv) = dk = c$, así $(x_0, y_0) = (ku, kv)$ es solución.

Ejemplo: ¿Tiene $6x + 10y = 15$ solución entera? $\gcd(6, 10) = 2$ y $2 \nmid 15$, así que no. ¿Y $6x + 10y = 14$? $\gcd(6,10) = 2$ y $2 \mid 14$, así que sí. Dividiendo por 2: $3x + 5y = 7$. Como $\gcd(3,5) = 1$, tiene soluciones para todo entero del lado derecho.

Encontrar una solución particular

Para encontrar una solución particular de $ax + by = c$ cuando $\gcd(a,b) \mid c$:

Paso 1. Dividir todo por $d = \gcd(a,b)$: la ecuación se convierte en $a'x + b'y = c'$ con $a' = a/d$, $b' = b/d$, $c' = c/d$ y $\gcd(a', b') = 1$.

Paso 2. Aplicar el algoritmo de Euclides extendido a $a'$ y $b'$ para encontrar $(u, v)$ con $a'u + b'v = 1$.

Paso 3. Multiplicar por $c'$: $(x_0, y_0) = (c'u, c'v)$ satisface $a'x_0 + b'y_0 = c'$.

Ejemplo: resolver $3x + 5y = 7$. Euclides extendido: $5 = 1 \cdot 3 + 2$; $3 = 1 \cdot 2 + 1$. Retrosustituir: $1 = 3 - 1 \cdot 2 = 3 - 1 \cdot (5 - 3) = 2 \cdot 3 - 5$. Así $3 \cdot 2 + 5 \cdot (-1) = 1$. Multiplicando por 7: $3 \cdot 14 + 5 \cdot (-7) = 7$. Solución particular: $(x_0, y_0) = (14, -7)$.

La solución general

Una vez encontrada una solución particular $(x_0, y_0)$ de $a'x + b'y = c'$ (con $\gcd(a',b')=1$), la solución general es:

$x = x_0 + b't, \quad y = y_0 - a't, \quad t \in \mathbb{Z}$.

Verificación: $a'(x_0 + b't) + b'(y_0 - a't) = a'x_0 + b'y_0 + a'b't - b'a't = c' + 0 = c'$.

Para ver que toda solución tiene esta forma: si $(x_1, y_1)$ también satisface $a'x_1 + b'y_1 = c'$, restando obtenemos $a'(x_1 - x_0) = -b'(y_1 - y_0)$. Como $\gcd(a',b')=1$, el teorema de Euclides implica $b' \mid (x_1 - x_0)$, es decir $x_1 - x_0 = b't$ para algún entero $t$, y análogamente $y_1 - y_0 = -a't$.

Ejemplo (continuación): la solución general de $3x + 5y = 7$ es $x = 14 + 5t$, $y = -7 - 3t$ para $t \in \mathbb{Z}$. Comprobando para $t = -2$: $x = 4$, $y = -1$; $3 \cdot 4 + 5 \cdot (-1) = 12 - 5 = 7$. Correcto.

Soluciones con restricciones: enteros positivos o acotados

En olimpiadas frecuentemente se pide encontrar soluciones con $x, y > 0$ (o con otras restricciones). Esto convierte el problema en encontrar los valores enteros de $t$ que satisfacen las desigualdades.

Ejemplo: ¿Cuántas soluciones en enteros positivos tiene $3x + 5y = 100$? De la solución general (con solución particular, por ejemplo $x_0 = 0, y_0 = 20$, pues $3 \cdot 0 + 5 \cdot 20 = 100$): $x = 5t$, $y = 20 - 3t$. Necesitamos $x > 0$: $t > 0$. Necesitamos $y > 0$: $20 - 3t > 0$, es decir $t < 20/3 \approx 6.67$, así $t \le 6$. Los valores válidos son $t \in \{1, 2, 3, 4, 5, 6\}$: hay exactamente 6 soluciones.

Una técnica útil: si el problema pregunta por el número de soluciones en enteros no negativos de $ax + by = n$ con $\gcd(a,b)=1$, ese número es aproximadamente $n/(ab)$ para $n$ grande, y oscila en $\pm 1$ alrededor de ese valor dependiendo de residuos.