Teorema Chino del Resto

El problema motivador

Un problema clásico chino del siglo III: "Hay cierta cantidad de objetos. Si los cuento de 3 en 3, sobran 2. Si los cuento de 5 en 5, sobran 3. Si los cuento de 7 en 7, sobran 2. ¿Cuántos objetos hay?" Esto es, encontrar $x$ tal que $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$, $x \equiv 2 \pmod{7}$.

La respuesta (mínima positiva) es $23$. Pero el verdadero poder del Teorema Chino del Resto (TCR) no es resolver este tipo de acertijo; es unificar dos cosas: (1) el álgebra de sistemas de congruencias, y (2) la descomposición $\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}$ cuando los $n_i$ son coprimos. Esta segunda lectura es lo que da al TCR su omnipresencia en olimpiadas.

El TCR tiene también un mensaje práctico: para probar que $n \mid f(a)$ para toda expresión $f$, basta probarlo separadamente para cada potencia prima en la factorización de $n$, y luego juntar los resultados.

Enunciado del Teorema Chino del Resto

Sean $n_1, n_2, \ldots, n_k$ enteros positivos mutuamente coprimos (es decir, $\gcd(n_i, n_j) = 1$ para $i \ne j$). Sea $N = n_1 n_2 \cdots n_k$. Entonces para cualesquiera enteros $a_1, a_2, \ldots, a_k$, el sistema

$x \equiv a_1 \pmod{n_1},\quad x \equiv a_2 \pmod{n_2},\quad \ldots,\quad x \equiv a_k \pmod{n_k}$

tiene **solución única módulo $N$**. Es decir, existe exactamente una clase de equivalencia módulo $N$ que satisface todas las congruencias.

La condición de coprimalidad mutua es necesaria: si $\gcd(n_1, n_2) = d > 1$, el sistema podría no tener solución (por ejemplo $x \equiv 0 \pmod{2}$ y $x \equiv 1 \pmod{4}$ es incompatible).

Demostración constructiva: el algoritmo

La demostración es constructiva y produce la solución explícitamente. Para cada $i$, define $M_i = N / n_i$ (el producto de todos los módulos excepto $n_i$). Como $\gcd(M_i, n_i) = 1$ (pues $n_i$ es coprimo con cada $n_j$, $j \ne i$), existe el inverso de $M_i$ módulo $n_i$: sea $y_i$ tal que $M_i y_i \equiv 1 \pmod{n_i}$.

La solución es $x = \sum_{i=1}^k a_i M_i y_i$. Verificación: módulo $n_j$, el $i$-ésimo sumando con $i \ne j$ contiene el factor $M_i$, que a su vez contiene $n_j$ como factor. Luego esos sumandos son $\equiv 0 \pmod{n_j}$. El sumando $i = j$ es $a_j M_j y_j \equiv a_j \cdot 1 = a_j \pmod{n_j}$. Perfecto.

La unicidad módulo $N$ es fácil: si $x$ y $x'$ son dos soluciones, entonces $n_i \mid x - x'$ para todo $i$. Como los $n_i$ son coprimos en pares, su producto $N$ divide $x - x'$, es decir $x \equiv x' \pmod{N}$.

Ejemplo trabajado

Resolvemos el sistema inicial: $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$, $x \equiv 2 \pmod{7}$.

$N = 3 \cdot 5 \cdot 7 = 105$. Los $M_i$ son: $M_1 = 35$, $M_2 = 21$, $M_3 = 15$.

Inversos: $35 \equiv 2 \pmod{3}$, necesitamos $2 y_1 \equiv 1 \pmod{3}$, luego $y_1 = 2$. $21 \equiv 1 \pmod{5}$, luego $y_2 = 1$. $15 \equiv 1 \pmod{7}$, luego $y_3 = 1$.

Solución: $x = 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233 \equiv 233 - 2 \cdot 105 = 23 \pmod{105}$.

Verificación: $23 = 7 \cdot 3 + 2$, $23 = 4 \cdot 5 + 3$, $23 = 3 \cdot 7 + 2$. Correcto en los tres módulos.

TCR como isomorfismo de anillos

Hay una manera más conceptual de ver el TCR: cuando $\gcd(m,n) = 1$, la función $\mathbb{Z}/mn\mathbb{Z} \to \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ dada por $[x]_{mn} \mapsto ([x]_m, [x]_n)$ es un isomorfismo de anillos. Esto significa que la aritmética módulo $mn$ "se descompone" en dos aritméticas independientes módulo $m$ y módulo $n$.

Esta perspectiva tiene consecuencias inmediatas. Por ejemplo, $\varphi(mn) = \varphi(m)\varphi(n)$ cuando $\gcd(m,n)=1$ se deduce directamente del isomorfismo: las unidades de $\mathbb{Z}/mn\mathbb{Z}$ se corresponden biyectivamente con pares de unidades en $\mathbb{Z}/m\mathbb{Z}$ y $\mathbb{Z}/n\mathbb{Z}$.

En olimpiadas, el uso más frecuente del TCR (en esta forma conceptual) es el siguiente: para demostrar que $n \mid f$ para alguna expresión $f$, basta demostrar $p^k \mid f$ para cada potencia prima $p^k \| n$ (es decir, $p^k \mid n$ pero $p^{k+1} \nmid n$). Después se "juntan" los resultados usando el TCR. Esta técnica es especialmente útil cuando $n$ tiene factores que se tratan con herramientas distintas (por ejemplo, PTF para $p$ y $q$ distintos).

TCR en problemas olímpicos: patrón de uso

El patrón más común en competencias es: "Encuentra todos los enteros $n$ tales que $n \mid f(n)$." La estrategia es descomponer $n$ en primos, aplicar condiciones de divisibilidad primo a primo usando PTF/Euler, y luego reensamblar con TCR.

Ejemplo olímpico (Iberoamericana 2002, adaptado): ¿Para cuáles primos $p$ y $q$ se tiene $p \mid q^2 + 1$ y $q \mid p^2 + 1$? La simetría del sistema sugiere $p = q$. Si $p = q$, entonces $p \mid p^2 + 1$, es decir $p \mid 1$, imposible para $p$ primo. Entonces $p \ne q$. Trabajando módulo $p$: $q^2 \equiv -1 \pmod{p}$, así que $-1$ es un residuo cuadrático módulo $p$, lo que por el criterio de Euler (anticipando la lección 5.1) requiere $p \equiv 1 \pmod{4}$ o $p = 2$. El análisis completo revela que la única solución es $\{p, q\} = \{2, 5\}$: $2 \mid 26 = 5^2+1$ y $5 \mid 5 = 2^2+1$.

El TCR aparece aquí implícitamente: la información sobre $p$ y $q$ separadamente se combina para obtener información global. En la práctica, cuando veas condiciones de divisibilidad que involucran varios primos, piensa en TCR.