Sistemas de Congruencias Lineales

Teoría

Un sistema de congruencias lineales se trata de varias condiciones que se deben cumplir al mismo tiempo para una variable entera $x$. En su forma más simple, buscas un entero $x$ que cumpla $x \equiv a_1 \pmod{m_1}, x \equiv a_2 \pmod{m_2}, \dots, x \equiv a_k \pmod{m_k}$. Aunque el Chinese Remainder Theorem (CRT) te garantiza una solución única cuando los módulos $m_i$ son primos relativos entre sí, los problemas de competencia suelen traer módulos que comparten factores comunes. En estos casos, no siempre vas a encontrar una solución; el sistema es consistente si y solo si las congruencias no se contradicen entre sí con respecto a los factores primos que los módulos tienen en común.

La técnica más confiable para resolver estos sistemas, sobre todo cuando los módulos no son primos relativos, es el método de sustitución sucesiva. La idea es reescribir la primera congruencia como una igualdad algebraica (por ejemplo, $x = m_1k + a_1$) y luego sustituir esa expresión en la segunda congruencia. Esto convierte el problema en una congruencia lineal para $k$. Ya que encuentres $k$, lo sustituyes de vuelta para hallar $x$ módulo $\text{lcm}(m_1, m_2)$. Repite este proceso paso a paso para cualquier otra congruencia que falte.

Entender cuándo existe una solución es clave para problemas de nivel AIME y olimpiada. Si tienes dos congruencias $x \equiv a \pmod m$ y $x \equiv b \pmod n$ que piden que $x$ tenga residuos distintos al dividirlo entre $\gcd(m,n)$, el sistema no tiene solución. En cambio, si se cumple la condición de consistencia, el sistema se reduce a una sola congruencia módulo $\text{lcm}(m,n)$. Esta reducción te permite simplificar sistemas complejos poco a poco hasta llegar a una sola condición que describe todas las soluciones.

Fórmulas Clave

Sistema General de Dos Congruencias Para el sistema: $$ \begin{cases} x \equiv a \pmod m \ x \equiv b \pmod n \end{cases} $$

Condición de Consistencia Vas a tener una solución si y solo si la diferencia de los residuos es divisible entre el máximo común divisor de los módulos: $$a \equiv b \pmod{\gcd(m,n)}$$

Unicidad y Módulo Si existe una solución $x_0$, la solución general es única módulo el mínimo común múltiplo de los módulos: $$x \equiv x_0 \pmod{\text{lcm}(m,n)}$$

Consistencia General (Múltiples Congruencias) Un sistema $x \equiv a_i \pmod{m_i}$ para $i=1, \dots, k$ tiene solución si y solo si: $$a_i \equiv a_j \pmod{\gcd(m_i, m_j)}$$ para todos los pares $i \neq j$. La solución es única módulo $\text{lcm}(m_1, m_2, \dots, m_k)$.

Demostración

Teorema: El sistema $x \equiv a \pmod m$ y $x \equiv b \pmod n$ tiene solución si y solo si $a \equiv b \pmod{\gcd(m,n)}$. Si tiene solución, la solución es única módulo $\text{lcm}(m,n)$.

Demostración:

1. Traducir a una Ecuación Diofántica: Puedes reescribir las congruencias como ecuaciones con parámetros enteros $y$ y $z$: $$x = my + a$$ $$x = nz + b$$ Si igualas las dos expresiones para $x$: $$my + a = nz + b \implies my - nz = b - a$$ Esta es una Ecuación Diofántica Lineal en las variables $y$ y $z$ de la forma $Ay + Bz = C$, donde $A=m$, $B=-n$ y $C=b-a$.

2. Condición de Existencia: Por la teoría de Ecuaciones Diofánticas Lineales, la ecuación $my - nz = b - a$ tiene soluciones enteras para $y$ y $z$ si y solo si $\gcd(m, -n)$ divide al término constante $b - a$. Como $\gcd(m, -n) = \gcd(m, n)$, vas a tener una solución si y solo si: $$\gcd(m,n) \mid (b - a)$$ Esto es equivalente a la condición de congruencia: $$a \equiv b \pmod{\gcd(m,n)}$$

3. Forma de la Solución: Supón que $d = \gcd(m,n)$. Si la condición se cumple, toma $y_0, z_0$ como una solución particular. La solución general para $y$ se ve así: $$y = y_0 + \frac{n}{d}t \quad \text{para algún entero } t$$ Al sustituir esto de vuelta en la expresión para $x$: $$x = m\left(y_0 + \frac{n}{d}t\right) + a = (my_0 + a) + \frac{mn}{d}t$$

4. Unicidad Módulo el MCM: Identifica el término constante $(my_0 + a)$ como una solución particular $x_0$. El coeficiente de $t$ es $\frac{mn}{d}$. Recuerda que $\text{lcm}(m,n) = \frac{mn}{\gcd(m,n)} = \frac{mn}{d}$. Por lo tanto, la solución general es: $$x = x_0 + \text{lcm}(m,n) \cdot t$$ En notación modular, esto queda como: $$x \equiv x_0 \pmod{\text{lcm}(m,n)}$$

   $\square$