Teorema chino del resto

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 Tzu.

Supongamos que n₁, n₂, …, n_k son enteros positivos coprimos dos a dos. Entonces, para enteros dados a₁,a₂, …, a_k, 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 ${displaystyle N=n_{1}n_{2}...n_{k}}$.

De manera más general, las congruencias simultáneas pueden ser resueltas si los n_i'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 n_i.

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=n₁n₂...n_k y sea ${displaystyle N_{i}={frac {N}{n_{i}}}}$ para i=1,...,k. Como todos los módulos n_i son coprimos entre sí, N_i y n_i son a su vez coprimos entre sí, luego por la Identidad de Bezout se asegura la existencia de dos enteros r_i y s_i tales que ${displaystyle r_{i}n_{i}+s_{i}N_{i}=1}$. 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 n_i, todos los sumandos se anulan a excepción del propio a_is_iN_i, y por tanto, ${displaystyle xequiv a_{i}{pmod {n_{i}}}}$ para todo i =1,...,k. De esta manera, queda demostrado que x es solución del sistema.

En el caso de que todos los n_i 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 ${displaystyle x-yequiv 0{pmod {n_{i}}}}$, y por ser todos los n_i coprimos, se sigue que el producto de los módulos N=n₁n₂...n_k también divide a x - y, es decir, ${displaystyle xequiv y{pmod {N}}}$.

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.

La forma original del teorema, contenida en un libro del siglo III por el matemático chino Sun Tzu^[2]​^[3]​ 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 ${displaystyle n}$, donde ${displaystyle n}$ es un producto de dos primos ${displaystyle p}$ y ${displaystyle q}$. Tamaños habituales para ${displaystyle n}$ son 1024, 2048 o 4096 bits, haciendo que los cálculos requieran una gran cantidad de tiempo. Usando el teorema chino del resto los cálculos pueden ser transportados del anillo ${displaystyle mathbf {Z} _{n}}$ al anillo ${displaystyle mathbf {Z} _{p} imes mathbf {Z} _{q}}$. La suma de las longitudes de bit de ${displaystyle p}$ y ${displaystyle q}$ es la longitud de bit de ${displaystyle n}$, haciendo ${displaystyle p}$ y ${displaystyle q}$ considerablemente menor que ${displaystyle n}$. Esto acelera mucho los cálculos. Nótese que las implementaciones del algoritmo RSA usando el teorema chino del resto son más susceptibles a ataques de "fault injection".