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.

Enunciado del teorema

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

${\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₁n₂...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_is_iN_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₁n₂...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₁, ..., 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".

Referencias

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

Enlaces externos

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

• Datos: Q193878