Teorema del Residuo Chino

Teoría

El Teorema del Residuo Chino (TRC) es un resultado fundamental en la teoría de números que te da una forma de resolver sistemas de congruencias lineales simultáneas con módulos que son coprimos entre sí. Te garantiza que un sistema así tiene una solución única módulo el producto de todos los módulos.

El teorema tiene orígenes antiguos, pues aparece en el texto matemático chino del siglo III "Sunzi Suanjing" con el problema: "Encuentra un número que deje un residuo de 2 al dividirlo entre 3, un residuo de 3 al dividirlo entre 5, y un residuo de 2 al dividirlo entre 7".

El TRC se usa muchísimo para:

• Resolver sistemas de congruencias.
• Simplificar cálculos módulo números grandes al dividirlos en módulos más pequeños.
• Criptografía (optimización de RSA).
• Ciencias de la computación (computación en paralelo).

Fórmulas Clave

Teorema del Residuo Chino:

Toma $n_1, n_2, \ldots, n_k$ como enteros positivos coprimos entre sí. Entonces, para cualesquiera enteros $a_1, a_2, \ldots, a_k$, el sistema: $$x \equiv a_1 \pmod{n_1}$$ $$x \equiv a_2 \pmod{n_2}$$ $$\vdots$$ $$x \equiv a_k \pmod{n