1.23: Teorema del resto chino
- Page ID
- 117471
El teorema del resto chino es un teorema importante que aparece quizás por primera vez en Sunzi Suanjing, un texto matemático chino escrito en algún momento durante los siglos III al V d.C. Ilustraremos su utilidad con una anécdota.
El hijo de un teórico del número está clasificando un gran montón de centavos (que valen menos de un dólar) en grupos de 3 centavos cada uno. Al final, el niño informa que quedan 2 centavos. El niño comienza de nuevo, en lugar de clasificar los centavos en grupos de 4 e informa que queda 1 centavo. El niño vuelve a empezar, clasificando los centavos en grupos de 11 y reporta que quedan 7 centavos. La teórica de números originalmente no sabía cuántos centavos había en la pila, pero en este punto ella habla.
¿Qué dice ella? ¿El niño cometió un error al clasificar los centavos? ¿O el teórico de los números tiene suficiente información para decir cuántos centavos hay en la pila?
Responderemos a esta pregunta con el Teorema del Resto Chino. Aquí está:
Dejar\(m_1,m_2,\dots,m_k\) ser números naturales de tal manera que cada uno sea mayor que 1, y cada par de ellos sea relativamente primo. Dejar\(M = m_1m_2\cdots m_k\), y dejar\(b_1,b_2,\dots,b_k\) ser enteros. El sistema de congruencias\[\begin{aligned} x &\equiv b_1 \pmod {m_1};\\ x &\equiv b_2 \pmod {m_2};\\ &\vdots\\ x &\equiv b_k \pmod {m_k};\\ \end{aligned}\] tiene una solución única en el conjunto\(\{0,1,2,\dots,M-1\}\).
Antes de probar el teorema, veamos qué pudo haber dicho el teórico de números de nuestra historia.
Supongamos que ese\(x\) es el número de centavos en la pila del niño. Si asumimos por un momento que el niño no cometió ningún error al clasificar los centavos en pilas, entonces\(x\) satisface las tres congruencias\[x \equiv 2 \pmod 3; \qquad x \equiv 1 \pmod 4; \qquad x \equiv 7 \pmod {11}.\nonumber \] En este punto, ya que los módulos 3, 4 y 11 tienen la propiedad de que cada dos son relativamente primos, afirma el Teorema del resto chino que hay una solución única a estas congruencias entre los enteros entre 0 y 131 (aquí\(3\cdot 4 \cdot 11 = 132\)). De hecho, se nos dice que hay un número positivo de centavos, pero hay menos de cien, así que exactamente un número en\(\{1,2,\dots,99\}\) puede ser nuestra solución al número de centavos.
Esto supone que el niño no cometió ningún error en el conteo, pero el teórico del número confía en su hijo (el niño ha sido entrenado desde el momento en que estaba en pañales para revisar su trabajo), y el Teorema del resto chino no puede señalar ningún error en los números en los lados de la derecha del congruencias (los residuos, no los módulos), ya que cada elección de estos números conduce a una solución.
En este punto el teórico del número sabe, como mínimo, que existe una solución única al sistema de congruencias. No obstante, si en este momento pudo decirle a su hijo cuántos centavos tiene, todavía no sabemos lo que dijo, porque el Teorema del Resto Chino por sí solo no nos dice cuál es la solución —solo que existe. Después de probar el Teorema del Resto Chino, discutiremos una manera práctica de resolver estos sistemas de congruencias, de encontrar la solución cuya existencia ha sido garantizada.
Prueba
Primero probamos que existe una solución en\(\{0,\dots,M-1\}\); lo haremos algorítmicamente.
Consideremos las dos primeras congruencias en el sistema:\[x \equiv b_1 \pmod {m_1}; \qquad x \equiv b_2 \pmod {m_2}.\nonumber \] Dado que\(m_1\) y\(m_2\) son relativamente primos, Lema de Bezout (Lema 1.9.1) implica que existen enteros\(s_1,t_1\) tales que\[\label{eq: Bzt 1} s_1m_1+t_1m_2 = 1.\] Encontramos estos enteros, quizás usando una técnica de la Sección 1.10. Una vez que tenemos, construimos una solución parcial\(x_2\) por\[x_2 = b_1t_1m_2 + b_2s_1m_1.\nonumber \] Nota aquí que hemos adjuntado las summands en ecuación\(\eqref{eq: Bzt 1}\) a los lados derecho de las congruencias, pero en el orden “opuesto”. Usamos el subíndice 2 y llamamos\(x_2\) una solución parcial porque satisface las dos primeras congruencias con las que comenzamos;\[\begin{aligned} x_2 &= b_1t_1m_2 + b_2s_1m_1\\ &\equiv b_1t_1m_2 \pmod {m_1}\\ &\equiv b_1(1-s_1m_1) \pmod {m_1}\\ &\equiv b_1 \pmod {m_1}, \end{aligned}\] y un argumento similar lo demuestra\(x_2 \equiv b_2 \pmod {m_2}\). Nuestro siguiente paso es registrar la información sobre nuestra solución parcial en su propia congruencia y emparejarla con la siguiente congruencia no utilizada de nuestro sistema:\[\begin{aligned} x &\equiv x_2 \pmod{m_1m_2};\\ x &\equiv b_3 \pmod{m_3}. \end{aligned}\] Resolvemos este par de congruencias de la misma manera que hicimos el primer par; ya que\(m_1m_2\) y no\(m_3\) podemos tener factores primos comunes, Lema de Bezout implica la existencia de enteros\(s_2,t_2\) tales que\[s_2(m_1m_2) + t_2m_3 = 1,\nonumber \] y nuestra siguiente solución parcial es\[x_3 = x_2t_2m_3 + b_3s_2(m_1m_2).\nonumber \] Es posible verificar que\(x_3\) satisfaga las congruencias módulo\(m_1\),\(m_2\), y \(m_3\). Una vez más pasamos al siguiente par de congruencias, utilizando nuestra solución parcial y la siguiente congruencia no utilizada:\[\begin{aligned} x &\equiv x_3 \pmod{m_1m_2m_3};\\ x &\equiv b_4 \pmod{m_4}. \end{aligned}\] Continuamos de esta manera hasta llegar a la solución parcial\(x_k\), que será una solución a todos\(k\) los originales\(k\) congruencias. Así el sistema tiene al menos una solución.
Ahora debemos demostrar la singularidad de la solución. Supongamos que\(x\) y\(y\) ambos eran congruentes con\(b_1\) módulo\(m_1\), congruentes con\(b_2\) módulo\(m_2\), y así sucesivamente. Entonces\(x \equiv y \pmod {m_i}\) para cada uno\(i\), es decir, que cada módulo\(m_i\) se divide\(x-y\). Dado que cada dos de los módulos son relativamente primos, esto implica (ver Ejercicio\(\PageIndex{1}\)) que\(m_1m_2\cdots m_k\) divide\(x-y\), lo que implica eso\(x \equiv y \pmod M\). Así sólo puede haber un elemento de\(\{0,1,2,\dots,M-1\}\) que es una solución al sistema de congruencias.
La existencia parte de la prueba del Teorema del Resto Chino nos da una forma de construir soluciones. Por favor, lea atentamente los pasos allí. Ilustramos la técnica con algunos ejemplos.
Resumiendo nuestro ejemplo anterior, resolvemos el sistema de congruencias\[x \equiv 2 \pmod 3; \qquad x \equiv 1 \pmod 4; \qquad x \equiv 7 \pmod {11}.\nonumber \] Comenzando con los dos primeros, encontramos coeficientes para el Lema de Bezout para los módulos 3 y 4, obteniendo\(-1\cdot 3 + 1 \cdot 4 = 1\). Construimos nuestra solución parcial\[x_2 = 2\cdot 4 + 1 \cdot -3 = 5.\nonumber \] Así\[x \equiv 5 \pmod {12} \qquad \text{and} \qquad x \equiv 7 \pmod{11}.\nonumber \] Ahora\(1 \cdot 12 - 1 \cdot 11 = 1\), así que nuestra siguiente solución parcial es\[x_3 = 5\cdot -11 + 7 \cdot 12 = 29.\nonumber \] Dado que hemos utilizado todas las congruencias originales, concluimos (y podemos verificar) que\(x=29\) es una solución al sistema de congruencias. El teórico del número responde a su hijo que su pila tiene exactamente 29 centavos.
Tenga en cuenta que la parte de singularidad del teorema del resto chino solo garantiza la singularidad de una solución entre las clases de residuos módulo\(M\). Por ejemplo, en nuestro ejemplo era necesario saber que había menos de 100 centavos, ya que\(x=161\) (\(=29+132\)),\(x=293\) (\(=29+2\cdot 132\)), y así sucesivamente también satisfacen todas las congruencias reportadas por el niño. En general, un sistema de congruencias que satisface los requisitos del Teorema del Resto Chino se satisface con un número infinito de enteros\(x\), aunque sólo uno de estos pertenece al conjunto\(\{0,1,\cdots,M-1\}\).
Ahora describamos todas las soluciones al sistema de congruencias\[\begin{aligned} 2x &\equiv 5 \pmod 7;\\ 4x &\equiv 5 \pmod 9;\\ x &\equiv 4 \pmod {11};\\ x &\equiv 8 \pmod {13}. \end{aligned}\] Este sistema aún no está listo para nuestra técnica a partir del ejemplo anterior, ya que las dos primeras congruencias tienen coeficientes extra a la izquierda. Podemos abordar este problema multiplicando la primera congruencia por la inversa de 2 módulo 7 (que es 4) y multiplicando la segunda congruencia por la inversa de 4 módulo 9 (que es 7), obteniendo\[\begin{aligned} x &\equiv 6 \pmod 7;\\ x &\equiv 8 \pmod 9;\\ x &\equiv 4 \pmod {11};\\ x &\equiv 8 \pmod {13}. \end{aligned}\] Comenzamos ahora con las dos primeras congruencias. Ya que\(4\cdot 7 - 3\cdot 9 = 1\), nuestra primera solución parcial es\(x_2 = 6\cdot -27 + 8\cdot 28 = 62\).
Trabajar ahora con\(x \equiv 62 \pmod {63}\) y\(x \equiv 4 \pmod {11}\), usando el Método de Blankinship o el Algoritmo Euclideano Extendido rinde\(-4 \cdot 63 + 23 \cdot 11 = 1\). Nuestra siguiente solución parcial es\(x_3 = 62\cdot 253 + 4 \cdot -252 = 14678\). Esto debería hacer que cada una de las tres primeras congruencias sean ciertas, pero es un número bastante grande; ¿tiene que ser así de grande?
Observe eso\(7\cdot 9 \cdot 11 = 693\), y rendimientos de división\(14678 = 21 \cdot 693 + 125\). Vamos\(x_3' = 125\). Veamos las congruencias con las\(x_3\) que satisface\(x_3'\) en lugar de\(x_3\):
| \(21 \cdot 693 + 125\) | \(\equiv\) | \(6\) | \(\pmod {7}\); | \(125\) | \(\equiv\) | \(6\) | \(\pmod {7}\); | |
| \(21 \cdot 693 + 125\) | \(\equiv\) | \(8\) | \(\pmod {9}\); | \(125\) | \(\equiv\) | \(8\) | \(\pmod {9}\); | |
| \(21 \cdot 693 + 125\) | \(\equiv\) | \(4\) | \(\pmod{11}\); | \(125\) | \(\equiv\) | \(4\) | \(\pmod{11}\). |
Ya que\(693\) es divisible por cada uno de\(7, 9, 11\), nuestra solución parcial\(x_3=14678\) tiene los mismos residuos módulo estos números que lo hace\(x'_3=125\), así que en adelante vamos a sustituir\(14678\) por\(125\).
Avanzando, el último par de congruencias que consideramos son\(x \equiv 125 \pmod {693}\) y\(x\equiv 8 \pmod {13}\). Un poco de cómputos rinde\(-3\cdot 693 + 160\cdot 13\), entonces\(x_4 = 125\cdot 2080 + 8\cdot -2079 = 243368\). Ya que\(7 \cdot 9 \cdot 11 \cdot 13 = 9009\), podemos sustituir este número por\(x'_4 = 243368\bmod 9009 = 125\).
Esta última solución parcial satisface las cuatro congruencias iniciales, y por el Teorema del resto chino, 125 es el único número en\(\{0,1,\dots,9008\}\) hacerlo. Sin embargo, la pregunta aquí es determinar todas las soluciones enteras a las congruencias. Estos son precisamente los enteros\(x\) para los cuales\(x \equiv 125 \pmod {9009}\), por lo que el conjunto de todas las soluciones es precisamente el conjunto\[\left\{125 + 9009n \mid n \in \mathbb{Z}\right\}.\nonumber \]
Ahora podemos dar una prueba de la afirmación del capítulo anterior de que si\(a\) y\(b\) son números enteros positivos relativamente primos, entonces\(\phi(ab) = \phi(a)\phi(b)\).
Considera el mapa\(f\) desde\(U_{ab}\) definido por\[f([x]) = ([x]_a,[x]_b),\nonumber \] donde\([x]_a\) y\([x]_b\) en el par ordenado indican las clases de residuos que contienen\(x\) en\(U_a\) y en\(U_b\), respectivamente. Observe que cada imagen debajo\(f\) es un par ordenado donde la primera entrada es una clase de residuo\(U_a\) (de la cual hay\(\phi(a)\) posibilidades) y la segunda entrada es una clase de residuo de\(U(b)\) (de la cual hay exactamente \(\phi(b)\)posibilidades). Así, existen\(\phi(a)\phi(b)\) posibles pares ordenados que podrían aparecer como los resultados del mapeo\(f\). Ahora podemos aplicar el Teorema del Resto Chino, ya que\(a\) y\(b\) son relativamente primos. Por cada par ordenado\(([c],[d])\) existe una solución única\(x\) módulo\(ab\) a las congruencias\(x \equiv c \pmod a\) y\(x \equiv d \pmod b\). Entonces por nuestra definición de\(f\) concluimos que\(f([x]) = ([c],[d])\), y\([x]\) es el único elemento de\(U_{ab}\) que se envía a\(([c],[d])\). Esto es cierto sin importar lo\(([c],[d])\) que sea, así que hay exactamente tantos elementos en\(U_{ab}\) como pares ordenados distintos\(([c],[d])\); así\(\phi(ab)=\phi(a)\phi(b)\).
Antes de terminar el capítulo mencionamos que el Teorema del Resto Chino es cierto en un contexto más general que el de los enteros. Para cierta clase más amplia de anillos \(^{1}\)(ver Apéndice C), si utilizamos nociones análogas de congruencia y relativa primeness, el Teorema del Resto Chino sigue siendo cierto. En particular, el Teorema es cierto para los enteros gaussianos (ver Ejercicio\(\PageIndex{6}\).
Ejercicios
Demostrar lo siguiente: si\(n\)\(m_1,m_2,\cdots, m_n\) y y\(N\) son todos enteros, y cada dos de\(m_1,m_2,\cdots,m_n\) son relativamente primos, y\(m_1,m_2,\cdots,m_n\) cada división\(N\), luego\(m_1m_2\cdots m_n\) divide \(N\).
(Pista: hay múltiples pruebas que se pueden dar, usando la factorización prima o el Lema e inducción de Bezout).
Describir todas las soluciones a los siguientes sistemas de congruencias.
- \(x \equiv 1 \pmod {8}\);\(x \equiv 2 \pmod 9\).
- \(3x \equiv 8 \pmod {10}\);\(x \equiv 13 \pmod {21}\).
Resuelve este problema atribuido a Euler: Encuentra dos números cuya suma sea 100 de tal manera que uno sea divisible por siete y el otro sea divisible por 11.
Dar todas las soluciones al sistema de congruencias:\[x \equiv 2 \pmod 3; \qquad x \equiv 2 \pmod 5; \qquad x \equiv 5 \pmod 7.\nonumber \]
- Explique por qué el sistema de congruencias no\[x \equiv 3 \pmod 6; \qquad x \equiv 4 \pmod 8\nonumber \] tiene solución. Explique por qué esto no viola el Teorema del Resto Chino.
- Encuentra todos los números en\(\{0,1,2,\dots,100\}\) que son soluciones al sistema de congruencias ¿\[x \equiv 2 \pmod 6; \qquad x \equiv 4 \pmod 8.\nonumber \]Puedes describir (y justificar) cuál es el conjunto de todas las soluciones enteras a este sistema de congruencias?
- ¿Se puede describir una moraleja a esta historia? Para usted, ¿qué ilustra este ejercicio sobre los sistemas de congruencias y el teorema del resto chino?
Usa ideas de este capítulo y de la Sección 1.13 (incluyendo los ejercicios) para resolver los siguientes sistemas de congruencias. Tus respuestas deben ser números enteros gaussianos.
- \(x \equiv i \pmod{1+i}\);\(x \equiv 2 \pmod {3i}\).
- \(x \equiv -3+i \pmod 5\);\(x \equiv -i \pmod {1-i}\).
Notas al pie
[1] A saber, los principales dominios ideales.