Teorema Chino del Resto

El Teorema Chino del Resto (al que nos referiremos como CRT en el resto de este artículo) fue descubierto por el matemático chino Sun Zi.

Formulación

Sea $m = m_1 \cdot m_2 \cdots m_k$, donde los $m_i$ son coprimos dos a dos. Además de los $m_i$, se nos da un sistema de congruencias

$$\left{$$$$\begin{array}{rcl} a & \equiv & a_1 \pmod{m_1} \ a & \equiv & a_2 \pmod{m_2} \ & \vdots & \ a & \equiv & a_k \pmod{m_k} \end{array}$$\right.

donde los $a_i$ son constantes dadas. La forma original del CRT afirma entonces que el sistema de congruencias dado siempre tiene una y exactamente una solución módulo $m$.

P. ej. el sistema de congruencias

$$\left{$$$$\begin{array}{rcl} a & \equiv & 2 \pmod{3} \ a & \equiv & 3 \pmod{5} \ a & \equiv & 2 \pmod{7} \end{array}$$\right.

tiene la solución $23$ módulo $105$, porque $23 \bmod{3} = 2$, $23 \bmod{5} = 3$ y $23 \bmod{7} = 2$. Podemos escribir todas las soluciones como $23 + 105\cdot k$ para $k \in \mathbb{Z}$.

Corolario

Una consecuencia del CRT es que la ecuación

$$x \equiv a \pmod{m}$$

es equivalente al sistema de ecuaciones

$$\left{$$$$\begin{array}{rcl} x & \equiv & a_1 \pmod{m_1} \ & \vdots & \ x & \equiv & a_k \pmod{m_k} \end{array}$$\right.

(Como arriba, suponemos que $m = m_1 m_2 \cdots m_k$ y que los $m_i$ son coprimos dos a dos).

Solución para dos módulos

Consideremos un sistema de dos ecuaciones para $m_1, m_2$ coprimos:

$$\left{$$$$\begin{align} a &\equiv a_1 \pmod{m_1} \ a &\equiv a_2 \pmod{m_2} \ \end{align}$$\right.

Queremos hallar una solución para $a \pmod{m_1 m_2}$. Usando el Algoritmo de Euclides extendido podemos hallar coeficientes de Bézout $n_1, n_2$ tales que

$$n_1 m_1 + n_2 m_2 = 1.$$

De hecho $n_1$ y $n_2$ son simplemente los inversos modulares de $m_1$ y $m_2$ módulo $m_2$ y $m_1$. Tenemos $n_1 m_1 \equiv 1 \pmod{m_2}$ así que $n_1 \equiv m_1^{-1} \pmod{m_2}$, y viceversa $n_2 \equiv m_2^{-1} \pmod{m_1}$.

Con esos dos coeficientes podemos definir una solución:

$$a = a_1 n_2 m_2 + a_2 n_1 m_1 \bmod{m_1 m_2}$$

Es fácil verificar que esto es efectivamente una solución calculando $a \bmod{m_1}$ y $a \bmod{m_2}$.

$$\begin{array}{rcll}a& \equiv & a_1{n}_2{m}_2+a_2{n}_1{m}_1& (\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)\\ & \equiv & a_1(1-n_1{m}_1)+a_2{n}_1{m}_1& (\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)\\ & \equiv & a_1-a_1{n}_1{m}_1+a_2{n}_1{m}_1& (\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)\\ & \equiv & a_1& (\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)\end{array}$$$$\begin{array}{rcll} a & \equiv & a_1 n_2 m_2 + a_2 n_1 m_1 & \pmod{m_1}\ & \equiv & a_1 (1 - n_1 m_1) + a_2 n_1 m_1 & \pmod{m_1}\ & \equiv & a_1 - a_1 n_1 m_1 + a_2 n_1 m_1 & \pmod{m_1}\ & \equiv & a_1 & \pmod{m_1} \end{array}$$

Nótese que el Teorema Chino del Resto también garantiza que existe solo 1 solución módulo $m_1 m_2$. Esto también es fácil de demostrar.

Supongamos que hay dos soluciones distintas $x$ e $y$. Como $x \equiv a_i \pmod{m_i}$ e $y \equiv a_i \pmod{m_i}$, se sigue que $x − y \equiv 0 \pmod{m_i}$ y por lo tanto $x − y \equiv 0 \pmod{m_1 m_2}$ o, de forma equivalente, $x \equiv y \pmod{m_1 m_2}$. Así que $x$ e $y$ son en realidad la misma solución.

Solución para el caso general

Solución inductiva

Como $m_1 m_2$ es coprimo con $m_3$, podemos aplicar de forma inductiva y repetida la solución para dos módulos para cualquier cantidad de módulos. Primero se calcula $b_2 := a \pmod{m_1 m_2}$ usando las dos primeras congruencias, luego se puede calcular $b_3 := a \pmod{m_1 m_2 m_3}$ usando las congruencias $a \equiv b_2 \pmod{m_1 m_2}$ y $a \equiv a_3 \pmod {m_3}$, etc.

Construcción directa

Es posible una construcción directa similar a la interpolación de Lagrange.

Sea $M_i := \prod_{i \neq j} m_j$, el producto de todos los módulos excepto $m_i$, y $N_i$ los inversos modulares $N_i := M_i^{-1} \bmod{m_i}$. Entonces una solución del sistema de congruencias es:

$$a \equiv \sum_{i=1}^k a_i M_i N_i \pmod{m_1 m_2 \cdots m_k}$$

Podemos comprobar que esto es efectivamente una solución calculando $a \bmod{m_i}$ para todo $i$. Como $M_j$ es un múltiplo de $m_i$ para $i \neq j$, tenemos

$$\begin{array}{rcll}a& \equiv & {\sum }_{j=1}^k{a}_j{M}_j{N}_j& (\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)\\ & \equiv & a_i{M}_i{N}_i& (\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)\\ & \equiv & a_i{M}_i{M}_i^{-1}& (\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)\\ & \equiv & a_i& (\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)\end{array}$$$$\begin{array}{rcll} a & \equiv & \sum_{j=1}^k a_j M_j N_j & \pmod{m_i} \ & \equiv & a_i M_i N_i & \pmod{m_i} \ & \equiv & a_i M_i M_i^{-1} & \pmod{m_i} \ & \equiv & a_i & \pmod{m_i} \end{array}$$

Implementación

struct Congruence {
    long long a, m;
};

long long chinese_remainder_theorem(vector<Congruence> const& congruences) {
    long long M = 1;
    for (auto const& congruence : congruences) {
        M *= congruence.m;
    }

    long long solution = 0;
    for (auto const& congruence : congruences) {
        long long a_i = congruence.a;
        long long M_i = M / congruence.m;
        long long N_i = mod_inv(M_i, congruence.m);
        solution = (solution + a_i * M_i % M * N_i) % M;
    }
    return solution;
}

Solución para módulos no coprimos

Como se mencionó, el algoritmo anterior solo funciona para módulos coprimos $m_1, m_2, \dots m_k$.

En el caso no coprimo, un sistema de congruencias tiene exactamente una solución módulo $\text{lcm}(m_1, m_2, \dots, m_k)$, o no tiene solución en absoluto.

P. ej. en el siguiente sistema, la primera congruencia implica que la solución es impar, y la segunda implica que la solución es par. No es posible que un número sea a la vez impar y par, por lo tanto claramente no hay solución.

$$\left{$$$$\begin{align} a & \equiv 1 \pmod{4} \ a & \equiv 2 \pmod{6} \end{align}$$\right.

Es bastante sencillo determinar si un sistema tiene solución. Y si la tiene, podemos usar el algoritmo original para resolver un sistema de congruencias ligeramente modificado.

Una sola congruencia $a \equiv a_i \pmod{m_i}$ es equivalente al sistema de congruencias $a \equiv a_i \pmod{p_j^{n_j}}$ donde $p_1^{n_1} p_2^{n_2}\cdots p_k^{n_k}$ es la factorización prima de $m_i$.

Con este hecho, podemos modificar el sistema de congruencias en un sistema que solo tiene potencias de primos como módulos. P. ej. el sistema de congruencias anterior es equivalente a:

$$\left{$$$$\begin{array}{ll} a \equiv 1 & \pmod{4} \ a \equiv 2 \equiv 0 & \pmod{2} \ a \equiv 2 & \pmod{3} \end{array}$$\right.

Como originalmente algunos módulos tenían factores comunes, obtendremos algunas congruencias con módulos basados en el mismo primo, aunque posiblemente con distintas potencias de primo.

Se puede observar que la congruencia con el módulo de mayor potencia de primo será la congruencia más fuerte de todas las basadas en el mismo número primo. O bien dará una contradicción con alguna otra congruencia, o ya implicará todas las demás.

En nuestro caso, la primera congruencia $a \equiv 1 \pmod{4}$ implica $a \equiv 1 \pmod{2}$, y por lo tanto contradice la segunda congruencia $a \equiv 0 \pmod{2}$. Por lo tanto este sistema de congruencias no tiene solución.

Si no hay contradicciones, entonces el sistema de ecuaciones tiene una solución. Podemos ignorar todas las congruencias excepto las que tienen los módulos de mayor potencia de primo. Estos módulos ahora son coprimos, y por lo tanto podemos resolver este sistema con el algoritmo discutido en las secciones anteriores.

P. ej. el siguiente sistema tiene una solución módulo $\text{lcm}(10, 12) = 60$.

$$\left{$$$$\begin{align} a & \equiv 3 \pmod{10} \ a & \equiv 5 \pmod{12} \end{align}$$\right.

El sistema de congruencias es equivalente al sistema:

$$\left{$$$$\begin{align} a & \equiv 3 \equiv 1 \pmod{2} \ a & \equiv 3 \equiv 3 \pmod{5} \ a & \equiv 5 \equiv 1 \pmod{4} \ a & \equiv 5 \equiv 2 \pmod{3} \end{align}$$\right.

Las únicas congruencias con el mismo módulo primo son $a \equiv 1 \pmod{4}$ y $a \equiv 1 \pmod{2}$. La primera ya implica la segunda, así que podemos ignorar la segunda y resolver en su lugar el siguiente sistema con módulos coprimos:

$$\left{$$$$\begin{align} a & \equiv 3 \equiv 3 \pmod{5} \ a & \equiv 5 \equiv 1 \pmod{4} \ a & \equiv 5 \equiv 2 \pmod{3} \end{align}$$\right.

Tiene la solución $53 \pmod{60}$, y en efecto $53 \bmod{10} = 3$ y $53 \bmod{12} = 5$.

Algoritmo de Garner

Otra consecuencia del CRT es que podemos representar números grandes usando un arreglo de enteros pequeños.

En lugar de hacer muchos cálculos con números muy grandes, lo cual puede ser costoso (pensemos en hacer divisiones con números de 1000 dígitos), se pueden elegir unos cuantos módulos coprimos y representar el número grande como un sistema de congruencias, y realizar todas las operaciones sobre el sistema de ecuaciones. Cualquier número $a$ menor que $m_1 m_2 \cdots m_k$ se puede representar como un arreglo $a_1, \ldots, a_k$, donde $a \equiv a_i \pmod{m_i}$.

Usando el algoritmo anterior, se puede reconstruir de nuevo el número grande cuando se necesite.

Como alternativa, se puede representar el número en la representación de base mixta (mixed radix):

$$a = x_1 + x_2 m_1 + x_3 m_1 m_2 + \ldots + x_k m_1 \cdots m_{k-1} \text{ with }x_i \in [0, m_i)$$

El algoritmo de Garner, que se discute en el artículo dedicado algoritmo de Garner, calcula los coeficientes $x_i$. Y con esos coeficientes se puede restaurar el número completo.

Problemas de práctica:

• Google Code Jam - Golf Gophers 
• Hackerrank - Number of sequences 
• Codeforces - Remainders Game