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.

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

${\displaystyle {\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 ${\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:

${\displaystyle 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

${\displaystyle 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^[1]​

${\displaystyle \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} .}$

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:

${\displaystyle {\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

${\displaystyle 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_is_iN_i, y por tanto, ${\displaystyle x\equiv 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:

${\displaystyle {\begin{aligned}x\equiv a_{i}{\pmod {n_{i}}}\\y\equiv a_{i}{\pmod {n_{i}}}\\\end{aligned}}}$

Esto implica que ${\displaystyle 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₁n₂...n_k también divide a x - y, es decir, ${\displaystyle 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.

El teorema chino de los restos se puede generalizar sobre cualquier Anillo ${\displaystyle R}$, mediante el concepto de ideales coprimos o comaximales.

Dos ideales I y J son coprimos si existen elementos ${\displaystyle i\in I}$ y ${\displaystyle j\in J}$ tales que ${\displaystyle 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:^[2]​^[3]​

Sean I₁, ..., I_k ideales bilateral de un anillo ${\displaystyle R}$ y sea I la intersección de los ideales . Si los ideales son coprimos dos a dos, se da el siguiente isomosrfismo:

${\displaystyle {\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 ${\displaystyle R/I}$ y el producto directo (o producto cartesiano) de los anillos ${\displaystyle R/I_{i},}$ donde "${\displaystyle x{\bmod {I}}}$" denota la imagen del elemento ${\displaystyle x}$ en el cociente del anillo definido por el ideal ${\displaystyle I.}$ Más aún, si ${\displaystyle R}$ es conmutativo, entonces la intersección de ideales coprimos dos a dos es igual a su producto; esto es:

${\displaystyle I=I_{1}\cap I_{2}\cap \cdots \cap I_{k}=I_{1}I_{2}\cdots I_{k},}$

Si ${\displaystyle I_{i}}$ y ${\displaystyle I_{j}}$ son coprimos para todo i ≠ j.

Sea ${\displaystyle R}$ un anilo conmutativo con unidad no trivial, e ${\displaystyle I_{1},I_{2},...,I_{n}}$ ideales coprimos. Entonces, para todo ${\displaystyle a_{1},...,a_{n}\in R}$ el sistema de congruencias

${\displaystyle {\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 ${\displaystyle R}$. Además si ${\displaystyle a}$ y ${\displaystyle b}$ son soluciones, entonces ${\displaystyle a-b\in I_{1}...I_{n}}$ (es decir, son congruentes), y recíprocamente si ${\displaystyle a}$ es solución e ${\displaystyle i\in I_{1}...I_{n}}$ entonces ${\displaystyle a+i}$ es solución.

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 ${\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}\times \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".

• Koblitz, Neal (1998). A Course in Number Theory and Cryptography (2ª edición). EE. UU.: Springer. pp. 238. ISBN 978-0-387-94293-3. 
• Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (2nd edición), Springer-Verlag, ISBN 0-387-97329-X .

• Weisstein, Eric W. .html «Chinese Remainder Theorem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.