# 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 Zi.

## Enunciado del teorema

Supongamos que n$_1$, n$_2$, …, n$_k$ son enteros positivos coprimos dos a dos. Entonces, para enteros dados a$_1$,a$_2$, …, a$_k$, existe un entero x que resuelve el sistema de congruencias simultáneas
    ${\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}$
Más aún, todas las soluciones x de este sistema son congruentes módulo el producto $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:
    $a_{i}\equiv a_{j}{\pmod {\operatorname {mcd} (n_{i},n_{j})}}\qquad {\text{para todo }}i\ {\text{y }}j.\,\!$
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
    $n=p_{1}^{r_{1}}\cdots p_{k}^{r_{k}},$
se tiene un isomorfismo entre un anillo y la suma directa de sus potencias primas
    $\mathbb {Z} /n\mathbb {Z} \cong \mathbb {Z} /p_{1}^{r_{1}}\mathbb {Z} \oplus \cdots \oplus \mathbb {Z} /p_{k}^{r_{k}}\mathbb {Z} .$

## Demostración del teorema
### Existencia de la solución

Sea N=n$_1$n$_2$...n$_k$ y sea $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 $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:
    ${\begin{aligned}s_{i}N_{i}\equiv 1{\pmod {n_{i}}}\\s_{i}N_{i}\equiv 0{\pmod {n_{j}}}\\\end{aligned}}$
Por tanto, definiendo
    $x:=\sum _{i=1}^{k}a_{i}s_{i}N_{i}=a_{1}s_{1}N_{1}+a_{2}s_{2}N_{2}+\ldots +a_{k}s_{k}N_{k},$
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$_i$s$_i$N$_i$, y por tanto, $x\equiv a_{i}{\pmod {n_{i}}}$ para todo i =1,...,k. De esta manera, queda demostrado que x es solución del sistema.

### Unicidad de la solución

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:
    ${\begin{aligned}x\equiv a_{i}{\pmod {n_{i}}}\\y\equiv a_{i}{\pmod {n_{i}}}\\\end{aligned}}$
Esto implica que $x-y\equiv 0{\pmod {n_{i}}}$, y por ser todos los n$_i$ coprimos, se sigue que el producto de los módulos N=n$_1$n$_2$...n$_k$ también divide a x - y, es decir, $x\equiv 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.

## Generalización para anillos

El teorema chino de los restos se puede generalizar sobre cualquier Anillo $R$, mediante el concepto de ideales coprimos o comaximales.
Dos ideales I y J son coprimos si existen elementos $i\in I$ y $j\in J$ tales que $i+j=1$.
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:
Sean I$_1$, ..., I$_k$ ideales bilateral de un anillo $R$ y sea I la intersección de los ideales . Si los ideales son coprimos dos a dos, se da el siguiente isomosrfismo:
    ${\begin{aligned}R/I&\to (R/I_{1})\times \cdots \times (R/I_{k})\\x{\bmod {I}}&\mapsto (x{\bmod {I}}_{1},\,\ldots ,\,x{\bmod {I}}_{k}),\end{aligned}}$
entre el anillo cociente
$R/I$ y el producto directo (o producto cartesiano) de los anillos $R/I_{i},$ donde "$x{\bmod {I}}$" denota la imagen del elemento $x$ en el cociente del anillo definido por el ideal $I.$ Más aún, si $R$ es conmutativo, entonces la intersección de ideales coprimos dos a dos es igual a su producto; esto es:
$I=I_{1}\cap I_{2}\cap \cdots \cap I_{k}=I_{1}I_{2}\cdots I_{k},$
Si $I_{i}$ y $I_{j}$ son coprimos para todo i ≠ j.

### Corolario: Teorema Chino de los Restos

Sea $R$ un anilo conmutativo con unidad no trivial, e $I_{1},I_{2},...,I_{n}$ ideales coprimos. Entonces, para todo $a_{1},...,a_{n}\in R$ el sistema de congruencias
${\begin{aligned}x&\equiv a_{1}{\pmod {I_{1}}}\\x&\equiv a_{2}{\pmod {I_{2}}}\\&\vdots \\x&\equiv a_{k}{\pmod {I_{k}}}\end{aligned}}$
admite una solución en $R$. Además si $a$ y $b$ son soluciones, entonces $a-b\in I_{1}...I_{n}$ (es decir, son congruentes), y recíprocamente si $a$ es solución e $i\in I_{1}...I_{n}$ entonces $a+i$ es solución.

## Historia

La forma original del teorema, contenida en un libro del siglo III por el matemático chino Sun Tzu 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).

## Aplicaciones en criptografía

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 $n$, donde $n$ es un producto de dos primos $p$ y $q$. Tamaños habituales para $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 $\mathbf {Z} _{n}$ al anillo $\mathbf {Z} _{p}\times \mathbf {Z} _{q}$. La suma de las longitudes de bit de $p$ y $q$ es la longitud de bit de $n$, haciendo $p$ y $q$ considerablemente menor que $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".