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. El enunciado dice:

Sean n,m \in \mathbb{N} tales que  \operatorname{mcd}(n, m) = 1 \, (primos relativos).

Entonces dados cualesquiera b_1,b_2 \in \mathbb{Z}, existe un x \in \mathbb{Z} tal que:

x \equiv b_1 \pmod n
x \equiv b_2 \pmod m

Y además, si existen otros v,w \in \mathbb{Z} que satisfagan las dos congruencias anteriores entonces:

v \equiv w \pmod {n \cdot m}

Enunciado del teorema[editar]

La forma original del teorema, contenida en un libro del siglo III por el matemático chino Sun Tzu[1] [2] y posteriormente publicado en 1247 por Qin Jiushao, es un enunciado sobre congruencias simultáneas (ver aritmética modular).

Sean b_1,b_2,...b_k\in\mathbb{Z} enteros cualquiera, y sean m_1,m_2,...m_k\in\mathbb{Z^{+}} módulos cualquiera. Entonces el sistema de ecuaciones congruentes:

\begin{align}
 x &\equiv b_1 \pmod{m_1} \\
 x &\equiv b_2 \pmod{m_2} \\
   &\vdots \\
 x &\equiv b_k \pmod{m_k}
\end{align}

Siempre tiene solución, y además es única en \pmod{\prod_{i=1}^{k}m_i}= \pmod{m_1\cdot m_2\cdots m_k}

Es decir, si x es tal solución, se verifica que [x]_{m_1}=[x]_{m_2}=\ldots=[x]_{m_k}

De manera más general, las congruencias simultáneas pueden ser resueltas si los m_i no son coprimos a pares. Una solución x existe si y sólo si:

b_i \equiv b_j \pmod{\operatorname{mcd}(m_i,m_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 m_i.

Versiones del teorema chino del resto fueron también conocidas por Brahmagupta, y aparecen en el Liber Abaci de Fibonacci (1202).

Demostración del teorema[editar]

Existencia de la solución[editar]

Sea M=\prod_{i=1}^{k}m_i=m_1\cdot m_2\cdots m_k y sea M_i=\frac{M}{m_i} \forall i=1\ldots k. Como todos los módulos m_i son coprimos entre sí, M_i y m_i son a su vez coprimos entre sí, luego por la Identidad de Bezout sabemos que \exists r_i,s_i\in\mathbb{Z}:r_im_i+s_iM_i=1.

En tales condiciones, tomando las clases de equivalencia en ambos lados, se tiene por un lado y por otro que:

\begin{align}
s_iM_i\equiv1\pmod{m_i} \\
s_iM_i\equiv0\pmod{m_j} \\
\end{align}

Por tanto, definiendo x=\sum_{i=1}^{k}b_is_iM_i=b_1s_1M_1+b_2s_2M_2+\ldots+b_ks_kM_k es claro que x es la solución buscada, debido a que al tomar clases de equivalencia en cada m_i, todos los sumandos se anulan a excepción del propio b_is_iM_i, y por tanto, x\equiv b_i\pmod{m_i} \forall i=1\ldots k.

Así pues, queda probado que x es solución del sistema. q.e.d

Unicidad de la solución[editar]

En el caso de que todos los m_i sean coprimos, esa solución es la única existente en \pmod{M}. Para demostrarlo, supongamos que existiesen dos soluciones distintas: \exists x,x'\in\mathbb{Z}. Entonces: \begin{align}
x\equiv b_i\pmod{m_i}&:\forall i=1\ldots k \\
x'\equiv b_i\pmod{m_i}&:\forall i=1\ldots k \\
\end{align}

Esto implica que m_i|(x-x'):\forall i=1\ldots k, y por ser todos los m_i coprimos, eso desemboca en que el producto de los módulos también divide a x-x', es decir, (\prod_{i=1}^{k}m_i=m_1m_2\cdots m_k)|(x-x')\longrightarrow M|(x-x')\longrightarrow x\equiv x'\pmod{M=\prod_{i=1}^{k}m_i=m_1m_2\cdots m_k}.

Por tanto, toda solución del sistema es congruente con x en \pmod{M}, tal y como se había establecido previamente en la formulación del Teorema. q.e.d

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. «Truth and Lies. Mapping the most complex known mathematical object» (en inglés). Higher Mathematics. The Economist (22/03/2007). Consultado el 26/12/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.».
  2. Ribnikov, Historia de las matemáticas, p. 42.

Referencias[editar]