Teorema chino del resto paso a paso: sistemas de congruencias

La idea

Un sistema de congruencias

$$x\equiv r_1\pmod{m_1},\quad \dots,\quad x\equiv r_k\pmod{m_k}$$

con módulos primos entre sí dos a dos tiene una única solución módulo $M=m_1\cdots m_k$.

La construcción

Para cada $i$ se toma $M_i=M/m_i$ (el producto de los demás módulos) y su inverso $y_i=M_i^{-1}\bmod m_i$, que existe porque $M_i$ y $m_i$ son primos entre sí. La solución es

$$x\equiv\sum_{i=1}^{k} r_i\,M_i\,y_i\pmod{M}.$$

Cada sumando vale $r_i$ módulo $m_i$ y $0$ módulo los demás, por eso la suma funciona.

Un ejemplo completo

Resolvamos

$$x\equiv1\pmod 4,\qquad x\equiv2\pmod 5,\qquad x\equiv3\pmod 7.$$

Aquí $M=4\cdot5\cdot7=140$.

$m_i$	$r_i$	$M_i$	$M_i \bmod m_i$	$y_i$	$r_iM_iy_i$
$4$	$1$	$35$	$3$	$3$	$105$
$5$	$2$	$28$	$3$	$2$	$112$
$7$	$3$	$20$	$6$	$6$	$360$

Por ejemplo, $y_1=3$ porque $35\cdot3=105\equiv1\pmod 4$. Sumando:

$$x\equiv105+112+360=577\equiv17\pmod{140}.$$

Comprobación: $17=4\cdot4+1=3\cdot5+2=2\cdot7+3$.

Errores típicos

• Aplicar la fórmula con módulos que no son coprimos: el inverso $y_i$ puede no existir. Hay que comprobar los $\operatorname{mcd}$ o resolver por sustitución.
• Calcular $y_i$ módulo $M$ en vez de módulo $m_i$.
• Olvidar reducir el resultado módulo $M$ (aquí $577$ y $17$ son la misma solución).
• Cambiar de sitio los restos $r_i$ y los módulos $m_i$.

Dónde se usa

Acelera el descifrado de RSA (se calcula módulo cada primo por separado) y permite repartir cálculos con números enormes. También sirve para problemas de calendarios y ciclos que se repiten con periodos distintos.