El teorema chino del resto es un resultado sobre congruencias en teoría de números y sus generalizaciones en álgebra abstracta.
Fue publicado por primera vez en el siglo III por el matemático chino Sun Zi.
Supongamos que n1, n2, …, nk son enteros positivos coprimos dos a dos.
Entonces, para enteros dados a1,a2, …, ak, existe un entero x que resuelve el sistema de congruencias simultáneas Más aún, todas las soluciones x de este sistema son congruentes módulo el producto
De manera más general, las congruencias simultáneas pueden ser resueltas si los ni's son coprimos a pares.
Una solución x existe si y solo si: Todas las soluciones x son entonces congruentes módulo el mínimo común múltiplo de los ni.
Un enunciado moderno en lenguaje algebraico es que para cada entero positivo con factorización en números primos se tiene un isomorfismo entre un anillo y la suma directa de sus potencias primas[1] Sea N=n1n2...nk y sea
para i=1,...,k. Como todos los módulos ni son coprimos entre sí, Ni y ni son a su vez coprimos entre sí, luego por la Identidad de Bezout se asegura la existencia de dos enteros ri y si tales que
En tales condiciones, tomando las clases de equivalencia en ambos lados de la identidad, se tiene que para cada i, y para cada j ≠ i: Por tanto, definiendo es claro que x es la solución buscada, debido a que al tomar clases de equivalencia en cada ni, todos los sumandos se anulan a excepción del propio aisiNi, y por tanto,
para todo i =1,...,k. De esta manera, queda demostrado que x es solución del sistema.
En el caso de que todos los ni sean coprimos, esa solución es la única existente módulo N. Para demostrarlo, supongamos que existiesen dos números enteros x e y que son soluciones distintas, entonces para i =1,2,...,k: Esto implica que
, y por ser todos los ni coprimos, se sigue que el producto de los módulos N=n1n2...nk también divide a x - y, es decir,
Por tanto, toda solución del sistema es congruente con x en módulo N, tal y como se había establecido previamente en la formulación del teorema.
El teorema chino de los restos se puede generalizar sobre cualquier Anillo
, mediante el concepto de ideales coprimos o comaximales.
Dos ideales I y J son coprimos si existen elementos
Esta relación sustituye a la identidad de bezout en las pruebas relacionadas con esta generalización, que son bastante parecidas a las relativas a números enteros.
La generalización puede enunciarse de la siguiente manera:[2][3] Sean I1, ..., Ik ideales bilateral de un anillo
y sea I la intersección de los ideales .
Si los ideales son coprimos dos a dos, se da el siguiente isomosrfismo: entre el anillo cociente
en el cociente del anillo definido por el ideal
son coprimos para todo i ≠ j. Sea
un anilo conmutativo con unidad no trivial, e
(es decir, son congruentes), y recíprocamente si
La forma original del teorema, contenida en un libro del siglo III por el matemático chino Sun Tzu[4][5] y posteriormente publicado en 1247 por Qin Jiushao, es un enunciado sobre congruencias simultáneas (ver aritmética modular).
Versiones del teorema chino del resto fueron también conocidas por Brahmagupta, y aparecen en el Liber Abaci de Fibonacci (1202).
El teorema del resto chino tiene importantes aplicaciones en criptografía, en especial para reducir operaciones con números enormes mediante el paso a congruencias.
En el algoritmo RSA, por ejemplo, los cálculos se hacen módulo
son 1024, 2048 o 4096 bits, haciendo que los cálculos requieran una gran cantidad de tiempo.
Nótese que las implementaciones del algoritmo RSA usando el teorema chino del resto son más susceptibles a ataques de "fault injection".