Teorema chino del resto

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[editar]

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

\begin{align}
 x &\equiv a_1 \pmod{n_1} \\
 x &\equiv a_2 \pmod{n_2} \\
   &\vdots \\
 x &\equiv a_k \pmod{n_k}
\end{align}

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 ni's no son coprimos a pares. Una solución x existe si y sólo si:

a_i \equiv a_j \pmod{\operatorname{mcd}(n_i,n_j)} \qquad \mbox{para todo }i\mbox{ y }j
. \,\!

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

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]

\mathbf{Z}/n\mathbf{Z} \cong \mathbf{Z}/p_1^{r_1}\mathbf{Z} \oplus \cdots \oplus \mathbf{Z}/p_k^{r_k}\mathbf{Z}.

Demostración del teorema[editar]

Existencia de la solución[editar]

Sea N=n1n2...nk y sea N_i=\frac{N}{n_i} 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 r_in_i+s_iN_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{align}
s_iN_i\equiv1\pmod{n_i} \\
s_iN_i\equiv0\pmod{n_j} \\
\end{align}

Por tanto, definiendo

x:=\sum_{i=1}^{k}a_is_iN_i=a_1s_1N_1+a_2s_2N_2+\ldots+a_ks_kN_k,

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, 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[editar]

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:

\begin{align}
x\equiv a_i\pmod{n_i}\\
y\equiv a_i\pmod{n_i}\\
\end{align}

Esto implica que x-y\equiv 0 \pmod{n_i}, 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, 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.

Historia[editar]

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

Aplicaciones[editar]

El teorema chino del resto 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 ó 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 \Bbb{Z}_n al anillo \Bbb{Z}_p \times \Bbb{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".

Notas[editar]

  1. Ireland y Rosen, 1990
  2. «Truth and Lies. Mapping the most complex known mathematical object». Higher Mathematics (en inglés). The Economist. 22 de marzo de 2007. Consultado el 26 de diciembre de 2011. «This theorem is contained in a book written in the late third-century AD by a mathematician called Sun Tzu (not to be confused with the military strategist of the same name). It is used to simplify large calculations by breaking them down into many smaller ones, the results of which can then be recombined to generate the answer to the original question.» 
  3. Ribnikov, Historia de las matemáticas, p. 42.

Referencias[editar]

  • Koblitz, Neal (1998). A Course in Number Theory and Cryptography (2ª edición). EE. UU.: Springer. p. 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[editar]