Diofánticas lineales y sistemas

La ecuación lineal diofántica

Una ecuación diofántica lineal es una ecuación de la forma $ax + by = c$ donde $a, b, c$ son enteros dados y se buscan soluciones enteras $(x, y)$. El nombre "diofántica" honra a Diofanto de Alejandría, quien estudió ecuaciones polinomiales con soluciones enteras o racionales en el siglo III.

La pregunta de existencia tiene una respuesta limpia: la ecuación $ax + by = c$ tiene solución entera si y solo si $\gcd(a, b) \mid c$. La condición es tanto necesaria (todo número de la forma $ax + by$ es múltiplo de $\gcd(a,b)$) como suficiente (la identidad de Bézout garantiza que $\gcd(a,b)$ se puede expresar como combinación lineal entera de $a$ y $b$).

El primer paso práctico es siempre: calcular $d = \gcd(a, b)$ con el algoritmo de Euclides, verificar que $d \mid c$, y dividir toda la ecuación por $d$ para obtener $a'x + b'y = c'$ con $\gcd(a', b') = 1$.

Encontrar una solución particular y el conjunto general

Para hallar una solución particular de $a'x + b'y = c'$ con $\gcd(a',b') = 1$, aplicamos el algoritmo de Euclides extendido para encontrar $x_0, y_0$ con $a'x_0 + b'y_0 = 1$, y luego multiplicamos por $c'$ para obtener $a'(c'x_0) + b'(c'y_0) = c'$.

Una vez obtenida una solución particular $(x_0, y_0)$, la solución general de $a'x + b'y = c'$ (con $\gcd(a',b') = 1$) es exactamente la familia parametrizada por $t \in \mathbb{Z}$:

Verificación: $a'(x_0 + b't) + b'(y_0 - a't) = a'x_0 + a'b't + b'y_0 - a'b't = c'$. Las flechas en las direcciones $+b'$ y $-a'$ reflejan el hecho de que el "núcleo" de la forma lineal $a'\cdot + b'\cdot$ es generado por $(b', -a')$.

El Teorema Chino del Resto

El Teorema Chino del Resto (TCR) generaliza el problema de solucionar sistemas de congruencias. En su forma más clásica: si $m_1, m_2, \ldots, m_k$ son enteros positivos coprimos dos a dos (es decir, $\gcd(m_i, m_j) = 1$ para $i \ne j$), entonces para cualesquiera enteros $a_1, a_2, \ldots, a_k$, el sistema

$x \equiv a_1 \pmod{m_1},\; x \equiv a_2 \pmod{m_2},\; \ldots,\; x \equiv a_k \pmod{m_k}$

tiene solución, y dicha solución es **única módulo $M = m_1 m_2 \cdots m_k$**. La solución explícita se construye como sigue: sea $M_i = M/m_i$ y sea $N_i$ el inverso de $M_i$ módulo $m_i$ (que existe porque $\gcd(M_i, m_i) = 1$). Entonces $x \equiv \sum_{i=1}^k a_i M_i N_i \pmod{M}$.

TCR para módulos no coprimos

Cuando los módulos no son coprimos, el sistema puede no tener solución. La condición general: el sistema $x \equiv a_1 \pmod{m_1}$, $x \equiv a_2 \pmod{m_2}$ tiene solución si y solo si $\gcd(m_1, m_2) \mid a_1 - a_2$.

Demostración: $x \equiv a_1 \pmod{m_1}$ y $x \equiv a_2 \pmod{m_2}$ equivale a $m_1 \mid x - a_1$ y $m_2 \mid x - a_2$. Escribiendo $x = a_1 + m_1 t$: $m_2 \mid a_1 + m_1 t - a_2$, es decir $m_1 t \equiv a_2 - a_1 \pmod{m_2}$, que es una ecuación lineal diofántica. Tiene solución si y solo si $\gcd(m_1, m_2) \mid a_2 - a_1$.

En problemas olímpicos, el TCR aparece a menudo para construir números con propiedades residuales específicas módulo varios primos a la vez, o para demostrar la existencia de soluciones a sistemas de congruencias.

Aplicación: ecuaciones lineales en problemas de olimpiada

Problema (Iberoamericana, estilo). Encuentra todos los enteros positivos $n$ menores que 1000 que satisfacen simultáneamente $n \equiv 3 \pmod{7}$ y $n \equiv 5 \pmod{11}$.

Solución. Como $\gcd(7, 11) = 1$, el TCR garantiza solución única módulo $77$. Buscamos $n = 7k + 3$ con $7k + 3 \equiv 5 \pmod{11}$, es decir $7k \equiv 2 \pmod{11}$. Como $7 \cdot 8 = 56 \equiv 1 \pmod{11}$, el inverso de 7 módulo 11 es 8. Entonces $k \equiv 8 \cdot 2 = 16 \equiv 5 \pmod{11}$, así $k = 11j + 5$ y $n = 7(11j + 5) + 3 = 77j + 38$. Los valores en $\{1, \ldots, 999\}$ son $n \in \{38, 115, 192, \ldots, 961\}$, que son $\lfloor (999 - 38)/77 \rfloor + 1 = 13$ valores.

El patrón: reducir a una ecuación lineal diofántica, aplicar el algoritmo de Euclides extendido, parametrizar, contar.

Soluciones positivas y acotadas

En muchos problemas olímpicos no basta con encontrar la familia general de soluciones: hay que determinar cuáles son positivas, o están en un intervalo dado, o satisfacen alguna condición adicional.

Para $ax + by = c$ con $a, b > 0$ y $c > 0$, la familia de soluciones enteras es $x = x_0 + bt$, $y = y_0 - at$. Para que ambas sean positivas: $x_0 + bt > 0$ y $y_0 - at > 0$, es decir $-x_0/b < t < y_0/a$. El número de soluciones en enteros positivos es la cantidad de enteros $t$ en este intervalo abierto.

Observación clave. Si $\gcd(a,b) = 1$ y $c = ab - a - b$, la ecuación $ax + by = c$ no tiene soluciones en enteros positivos (es el "número de Frobenius" de $a$ y $b$: el mayor número no representable como $ax + by$ con $x, y \ge 0$). Esta observación tiene su propia historia olímpica.

Estrategia general para ecuaciones diofánticas lineales

Al enfrentarse a una ecuación diofántica o sistema lineal en olimpiadas, el protocolo es:

Paso 1. Calcular $d = \gcd(a,b)$. Si $d \nmid c$, no hay solución (respuesta: imposible).

Paso 2. Dividir por $d$: estudiar $a'x + b'y = c'$ con $\gcd(a',b') = 1$.

Paso 3. Aplicar Euclides extendido para encontrar $(x_0, y_0)$ con $a'x_0 + b'y_0 = 1$. La solución particular de la ecuación original es $(c'x_0, c'y_0)$.

Paso 4. Escribir la familia general $x = c'x_0 + b't$, $y = c'y_0 - a't$.

Paso 5. Aplicar las condiciones adicionales (positividad, acotamiento, paridad, congruencias) para filtrar los valores válidos de $t$.