Teorema chino del residuo

Introducción

En este capítulo vamos a ver bajo qué condiciones podemos encontrar un valor \(x\) que satisface varias congruencias simultáneamente. En otras palabras vamos a resolver un sistema de congruencias lineales. Para este capítulo, retomaremos el concepto de mínimo común múltiplo. Veremos algunos resultados que se derivan de éste y que nos serán útiles para demostrar el teorema principal.

El teorema chino del residuo es el protagonista de este capítulo. Nos sirve para encontrar la solución única de un sistema de congruencias del tipo \(x\equiv a_i\pmod{m_i}\), donde los valores \(m_i\) son primos relativos por pares para \(i = 1, 2, \ldots ,n\). Empezaremos con un ejercicio en donde resolvemos un sistema de congruencias sin usar el teorema chino del residuo, con la finalidad de mostrar que es una herramienta muy útil para los sistemas de congruencias lineales en donde se involucran más de \(3\) congruencias. Al final de capítulo veremos algunas aplicaciones del teorema chino del residuo.

Resultados previos

En la Definición 15 del mínimo común múltiplo, tenemos que si los enteros \(a\) y \(b\) tienen algún múltiplo en común \(c\), entonces \([a,b]|c\). Es decir, que el valor de \([a,b]\) es el más pequeño de todos los múltiplos positivos que tienen en común \(a\) y \(b\). Vamos a generalizar este hecho.

Corolario 11

Si \(b\) es cualquier múltiplo común de los enteros positivos \(a_1, a_2, \ldots , a_n\), entonces \([a_1, a_2, \ldots ,a_n]|b\)

Demostración. Denotemos como \(h\) a \([a_1, a_2, \ldots ,a_n]\) y sea \(b\) cualquier múltiplo común de los enteros positivos \(a_1, a_2, \ldots , a_n\).
Si \(b\) lo dividimos entre \(h\), por el algoritmo de la división existen \(q\) y \(r\) tales que \(b = qh + r\), donde \(0\le r < h\). Debemos demostrar que \(r = 0\).
En búsqueda de una contradicción, vamos a suponer que \(r \neq 0\).
Como \([a_1, a_2, \ldots ,a_n] = h\), para cada \(i = 1,2, \ldots n\) sabemos que \(a_i|h\) y como \(b\) es un múltiplo común de todos los \(a_i\) tenemos que \(a_i|b\), por lo tanto \(a_i|r\). Así, \(r\) es un múltiplo común de \(a_1, a_2, \ldots , a_n\). Pero entonces \(r < h\), y esto contradice el hecho de que \(h\) sea el mínimo común múltiplo. Por lo tanto tenemos una contradicción y así \(r = 0\).

Por lo tanto, \(b = qh\) y así \([a_1, a_2, \ldots ,a_n]|b\). \(\square\)

Con ayuda del Corolario 11 y de la recursividad podemos extender la idea del mínimo común múltiplo para \(3\) o más números.

Teorema 47

Sean \(a_1,a_2,\ldots , a_n\) enteros positivos, donde \(n\ge 3\). Entonces

\[[a_1,a_2,\ldots ,a_n] = [[a_1,a_2,\ldots ,a_{n-1}],a_n].\]

Demostración. Sean \(l = [a_1,a_2,\ldots ,a_n]\), \(l' = [a_1,a_2,\ldots ,a_{n-1}]\) y \(l'' = [l',a_n]\). Vamos a demostrar que \(l = l''\).

• Primero demostremos que \(l''|l\).

Como \(l = [a_1,a_2,\ldots ,a_n]\), tenemos que \(a_i|l\) para \(i = 1,2,\ldots ,n\). Luego, \(a_i|l\) si tomamos \(i = 1,2,\ldots ,n-1\), tendríamos que \(l\) es un múltiplo en común de esas \(a_i\). Pero \(l' = [a_1,a_2,\ldots ,a_{n-1}]\), entonces por la Definición 15 \(l'|l\). Además, ya teníamos que \(a_n|l\). Así, \(l\) es un múltiplo en común de \(l'\) y \(a_n\). Por lo tanto, como \(l'' = [l',a_n]\), por definición concluimos que \(l''|l\).

• Ahora, demostremos que \(l\|l''\).

Como \(l'' = [l',a_n]\), tenemos que \(l'|l''\) y \(a_n|l''\). Luego, como \(l' = [a_1,a_2,\ldots ,a_{n-1}]\), entonces \(a_i|l'\) para \(i = 1,2,\ldots ,n-1\). Por el inciso \(2\) de la Proposición 2, tendremos que \(a_i|l''\) para \(i = 1,2,\ldots n-1\). Por lo anterior, tenemos que \(a_i|l''\) para \(i = 1,2,\dots ,n\), en otras palabras, \(l''\) es un múltiplo en común de \(a_i\) con \(i = 1,2,\ldots ,n\). Por lo tanto, como \(l = [a_1,a_2,\ldots ,a_n]\) por definición concluimos que \(l|l''\).

Hemos demostrado que \(l''|l\) y \(l|l''\), por lo tanto \(l = l''\). \(\square\)

El siguiente resultado se dejó como ejercicio en el capítulo del teorema fundamental de la aritmética.

Teorema 48

Sean \(a\) y \(b\) enteros positivos, entonces

\[[a,b] = \frac{ab}{(a,b)}.\]

Si no lo haz demostrado, es un buen momento para hacerlo, ya que nos será de ayuda para los siguientes resultados.

Con el mínimo común múltiplo también podemos decir si dos enteros \(a\) y \(b\) son primos relativos, como se muestra en el siguiente corolario.

Corolario 12

Dos enteros positivos \(a\) y \(b\) son primos relativos si y sólo si \([a,b] = ab\).

Demostración. Por el Teorema 48, tenemos que

\[[a,b] = \frac{ab}{(a,b)}.\]

Luego, el resultado se obtiene directo ya que, \((a,b) = 1\) si y sólo si \([a,b] = ab\). \(\square\)

Para finalizar esta sección, vamos a generalizar el Corolario 12.

Corolario 13

Sea \(n \ge 2\) entero. Si los enteros positivos \(a_1,a_2,\ldots ,a_n\) son primos relativos por pares, entonces

\[[a_1, a_2,\ldots ,a_n] = a_1a_2\cdot \ldots \cdot a_n.\]

Demostración. Vamos a proceder por inducción.

Sea \(P(n)\) la proposición que afirma que para el entero positivo \(n\) se cumple que

\[[a_1, a_2,\ldots ,a_n] = a_1a_2\cdot \ldots \cdot a_n.\]

Base inductiva. En el Corolario 12 ya demostramos que si \(a_1\) y \(a_2\) son primos relativos, entonces \([a_1, a_2] = a_1a_2.\) Por lo tanto, \(P(2)\) es verdadera.

Hipótesis inductiva. Supongamos que \(P(n)\) es verdadera para algún entero positivo \(n\), es decir, que si los enteros positivos \(a_1,a_2,\ldots ,a_n\) son primos relativos por pares, entonces

\[[a_1, a_2,\ldots ,a_n] = a_1a_2\cdot \ldots \cdot a_n.\]

Paso inductivo. Ahora lo que queremos probar es que \(P(n)\) implica \(P(n+1)\). Entonces dados los enteros \(a_1, a_2, \ldots ,a_{n+1}\) queremos llegar a que \([a_1, a_2,\ldots ,a_n,a_{n+1}] = a_1a_2\cdot \ldots \cdot a_n\cdot a_{n+1}\).

Por el Teorema 47, sabemos que

\[[a_1, a_2, \ldots ,a_{n+1}] = [ [a_1, a_2, \ldots ,a_n] ,a_{n+1}].\]

Luego, por el Teorema 48 tenemos que se cumple lo siguiente,

\[[ [a_1, a_2, \ldots ,a_n] ,a_{n+1}] = \frac{[a_1, a_2, \ldots ,a_n] \cdot a_{n+1}}{\left( (a_1, a_2, \ldots ,a_n) , a_{n+1} \right)}.\]

Ahora, por el Teorema 7 \((a_1,a_2, \ldots, a_n, a_{n+1}) = ((a_1, a_2, \ldots ,a_n),a_{n+1})\). Por otro lado, con el cor-prim-rel-par tenemos que \((a_1,a_2, \ldots, a_n, a_{n+1}) = 1\). La hipótesis inductiva, dice que \([a_1, a_2,\ldots ,a_n] = a_1a_2\cdot \ldots \cdot a_n\). Tendríamos entonces

\[\begin{align*} [ [a_1, a_2, \ldots ,a_n] ,a_{n+1}] &= \frac{[a_1, a_2, \ldots ,a_n] \cdot a_{n+1}}{\left( (a_1, a_2, \ldots ,a_n) , a_{n+1} \right)} \\ & \\ &= \frac{ a_1a_2\cdot \ldots \cdot a_n\cdot a_{n+1}}{ (a_1, a_2, \ldots ,a_n, a_{n+1})} \\ & \\ &= \frac{ a_1a_2\cdot \ldots \cdot a_n\cdot a_{n+1}}{1}. \end{align*}\]

Por lo tanto, si \(P(n)\) es verdadera, entonces \(P(n+1)\) es también verdadera. Así, por inducción, \(P(n)\) es verdadera para todo entero \(n \geq 2\). \(\square\)

Ejemplo para dos módulos

En el capítulo de resolución congruencias lineales vimos la Definición 41 de congruencia lineal y cómo encontrar una solución para ésta. Pero, ¿qué pasaría si tuviéramos las congruencias \(a_1x\equiv b_1\pmod{m_1}\), \(a_2x\equiv b_2\pmod{m_2}\) y quisiéramos encontrar un valor de \(x\) que satisfaga ambas congruencias? Lo anterior formaría un sistema de congruencias lineales.

Definición 42 (Sistema de congruencias lineales)

Sean \(a_i, b_i\) y \(m_i\) números enteros para \(i = 1,2,\ldots ,k\) y \(x\) una incognita. Un sistema de congruencias lineales es de la forma

\[\begin{align*} a_1x &\equiv b_1\pmod{m_1}, \\ & \\ a_2x &\equiv b_2\pmod{m_2}, \\ & \vdots \\ a_kx &\equiv b_k\pmod{m_k}. \end{align*}\]

El objetivo es encontrar el valor de \(x\) que cumpla todas las congruencias.

Observación 17

Como vimos en el Teorema 44, bajo la suposición de que \((a_i,m_i) = 1\) para \(i = 1,2, \ldots ,k\), el sistema anterior se podría reducir a la forma

\[\begin{align*} x &\equiv c_1\pmod{m_1}, \\ & \\ x &\equiv c_2\pmod{m_2}, \\ & \vdots \\ x &\equiv c_n\pmod{m_k}, \end{align*}\]

donde \(c_i \equiv a_i^{-1}b_i\pmod{m_i}\), para \(i = 1,2,\ldots ,k\).

En la solución de esta clase de sistemas, el teorema chino del residuo juega un papel importante. Pero antes de introducirlo, veamos algunos ejercicios.

Ejemplo 120

Para introducir la idea del teorema principal pensemos en el siguiente problema. Supongamos que queremos encontrar un número \(x\) que cumpla con la siguientes dos condiciones.

1. Al dividir \(x\) entre \(21\) el residuo es \(5\).

2. Al dividir \(x\) entre \(58\) el residuo es \(19\).

Lo anterior se puede traducir en las siguientes congruencias.

\[\begin{split}\begin{cases} x \equiv 5 \pmod{21}, \\ & \\ x \equiv 19 \pmod{58}. \end{cases}\end{split}\]

Para encontrar el valor de \(x\), vamos a seguir el siguiente algoritmo de iteración. Notemos que \((21,58) = 1.\)

Como \(x\equiv 5\pmod{21}\), por el Teorema 28 tenemos que \(x = 5 + 21u\) y esto podemos sustituirlo en la segunda congruencia obteniendo que

\[\begin{align*} x&\equiv 19\pmod{58}, \\ & \\ 5 + 21u&\equiv 19\pmod{58}, \\ & \\ 21u&\equiv 19 - 5\pmod{58}, \\ & \\ 21u&\equiv 14\pmod{58}. \\ \end{align*}\]

Ahora sólo falta buscar el inverso de \(21\) módulo \(58\), el cual es \(47\), ya que \(21\cdot 47 = 987\equiv 1\pmod{58}\). Entonces multiplicamos la congruencia por \(47\) en ambos lados y tenemos que

\[\begin{align*} 21u\equiv 14\pmod{58}, \\ & \\ 47\cdot 21u\equiv 47\cdot 14\pmod{58}, \\ & \\ u\equiv 658\pmod{58}, \\ & \\ u\equiv 20\pmod{58}. \end{align*}\]

Nuevamente, como \(u\equiv 20\pmod{58}\) tenemos que \(u = 20 + 58v\).

Por lo tanto, tenemos que

\[x = 5 + 21u = 5 + 21(20 + 58v) = 5 + 420 + 1218v = 425 + 1218v,\]

satisface ambas congruencias para cualquier valor de \(v\).

Si tomamos \(v = 0\), podemos verificar que

\[425\equiv 5\pmod{21} \quad \text{ y } \quad 425\equiv 19\pmod{58}.\]

Notemos que para este caso la solución particular sería \( x_0 = 425\) y la solución general tendría la forma \(x = x_0 + (21\cdot 58)t\), lo cual quiere decir que la solución pertenece a la clase de congruencia \([425]_{1218}\).

Para mostrar qué pasaría si los módulos no son primos relativos, veamos el siguiente ejemplo.

Ejemplo 121

Prueba que el siguiente sistema de congruencias no tiene solución.

\[\begin{split}\begin{cases} x\equiv 3\pmod{9}, \\ & \\ x\equiv 2\pmod{6}. \end{cases}\end{split}\]

Solución.

Como \(x\equiv 3\pmod{9}\), entonces tenemos que \(x = 3 + 9u\). Si sustituimos esto en la segunda congruencia obtenemos que

\[\begin{align*} x &\equiv 2\pmod{6}, \\ & \\ 3 + 9u &\equiv 2\pmod{6}, \\ & \\ 9u &\equiv 2 - 3\pmod{6}, \\ & \\ 9u &\equiv -1\pmod{6}, \\ & \\ 3u &\equiv 5\pmod{6}. \\ \end{align*}\]

El problema es que no podemos despejar el valor de \(u\) ya que, por el Teorema 34, \(3\) no tiene inverso módulo \(6\) ya que \((3,6) = 3\). Además, por el Teorema 43 sabemos que no hay solución ya que \(3\nmid 5\)

Aún así, si continuamos con el algoritmo. Como \(3u\equiv 5\pmod{6}\), tenemos que \(3u = 5 + 6v\).
Por lo tanto, tendremos

\[x = 3 + 9u = 3 + 3(3u) = 3 + 3 (5 + 6v) = 3 + 15 + 18v = 18 + 18v.\]

Si tomamos \(v = 0\), tendríamos que \(x = 18\). Pero \(18\not\equiv 3\pmod{9}\) y \(18\not\equiv 2\pmod{6}\).

En esta sección vamos a ver que podemos resolver sistemas de congruencias como los mencionados en la Observación 17. Pero con la condición de que los valores de \(m_i\) sean primos relativos por pares para \(i = 1,2,\ldots ,k\). Veamos el teorema para dos congruencias.

Teorema 49

Si \(n\) y \(m\) son enteros primos relativos, entonces las congruencias

\[\begin{split}\begin{cases} x \equiv a\pmod{m}, \\ & \\ x \equiv b\pmod{n}, \end{cases}\end{split}\]

tienen solución en común.

Demostración. Por el Teorema 28, sabemos que la congruencia \(x\equiv a\pmod{m}\) la podemos representar como \(x = a + km\), en donde \(k\) es un entero.
Sustituyendo esto en la segunda congruencia tendríamos que

\[\begin{align*} x &\equiv b\pmod{n}, \\ & \\ a + km &\equiv b\pmod{n}, \\ & \\ km &\equiv b - a\pmod{n}. \\ \end{align*}\]

Luego como \((m,n) = 1\), sabemos que \(m\) tiene inverso módulo \(n\), digamos \(m'\). Entonces multiplicamos la congruencia por \(m'\) y tendríamos que

\[\begin{align*} (km)m' &\equiv (b - a)m'\pmod{n}, \\ & \\ k &\equiv (b - a)m'\pmod{n}. \end{align*}\]

La congruencia anterior la podemos expresar como \(k = (b - a)m' + tn\) para algún entero \(t\).

Entonces tendríamos que

\[x = a + km = a + ((b - a)m' + tn)m = a + (b - a)m'm + tnm.\]

Verifiquemos que está solución satisface ambas congruencias.

Ya que \(m|[(b - a)m'm]\) y \(m|tnm\) sucede que \((b - a)m'm\equiv tnm \equiv 0\pmod{m}\), entonces

\[x \equiv a + (b - a)m'm + tnm \equiv a + 0 + 0 \equiv a\pmod{m}.\]

Luego como \(mm' \equiv 1 \pmod{n}\) y como \(n|tnm\), tenemos que \(tnm\equiv 0\pmod{n}\). Entonces

\[x \equiv a + (b - a)m'm + tnm \equiv a + (b-a)\cdot 1 + 0 \equiv a + b - a\equiv b\pmod{n}.\]

Por lo tanto las congruencias \(x\equiv a\pmod{m}\) y \(x\equiv b\pmod{n}\) tienen una solución en común. \(\square\)

Teorema chino del residuo

Observemos que el algoritmo visto en el Ejemplo 120 también podemos utilizarlo para encontrar el valor de \(x\) que satisface \(3\) congruencias. El siguiente ejemplo es el acertijo del matemático Chino Sun-Tsu. Después de esto veremos el teorema principal de esta sección.

Ejemplo 122

Encuentra el valor de \(x\) que satisface las siguientes congruencias,

\[\begin{split}\begin{cases} x\equiv 1\pmod{3}, \\ & \\ x\equiv 2\pmod{5}, \\ & \\ x\equiv 3\pmod{7}. \end{cases}\end{split}\]

Solución.

Ya que \(x\equiv 1\pmod{3}\), por el Teorema 28 tenemos que \(x = 1 + 3t_1\), en donde \(t_1\) es un entero arbitrario. Vamos a sustituir esto en la congruencia \(x\equiv 2\pmod{5}\), obteniendo que

\[\begin{align*} x &\equiv 2\pmod{5}, \\ & \\ 1 + 3t_1 &\equiv 2\pmod{5}, \\ & \\ 3t_1 &\equiv 2 - 1 \pmod{5}, \\ & \\ 3t_1 &\equiv 1 \pmod{5}. \end{align*}\]

Buscamos el inverso de \(3\) módulo \(5\), el cual es \(2\) ya que \(3\cdot 2 = 6 \equiv 1\pmod{5}.\) Entonces llegamos a que

\[\begin{align*} 3t_1 &\equiv 1 \pmod{5}, \\ & \\ 2\cdot 3t_1 &\equiv 2\cdot 1 \pmod{5}, \\ & \\ t_1&\equiv 2\pmod{5}. \end{align*}\]

Ahora como \(t_1\equiv 2\pmod{5}\), podemos decir que \(t_1 = 2 + 5t_2\), con \(t_2\) un entero arbitrario. Vamos a sustituir este valor en \(x\), teniendo que

\[x = 1 + 3t_1 = 1 + 3(2 + 5t_2) = 1 + 6 + 15t_2 = 7 + 15t_2.\]

Nuevamente vamos a sustituir esto, ahora en la congruencia \(x\equiv 3\pmod{7}\), obteniendo lo siguiente

\[\begin{align*} x &\equiv 3\pmod{7}, \\ & \\ 7 + 15t_2 &\equiv 3\pmod{7}, \\ &\\ 0 + t_2 &\equiv 3\pmod{7}, \\ & \\ t_2&\equiv 3\pmod{7}. \end{align*}\]

Con lo anterior, como \(t_2\equiv 3\pmod{7}\), tenemos que \(t_2 = 3 + 7t.\) Finalmente, sustituimos esto en el valor de \(x\) obteniendo que

\[x = 7 + 15t_2 = 7 + 15(3 + 7t) = 7 + 45 + 105t = 52 + 105t.\]

Así, obtenemos que cualquier entero de la forma \(x = 52 + 105t\) satisface las 3 congruencias. Se puede comprobar que para \(t = 0\), \(x = 52\) y se cumple que

\[52\equiv 1\pmod{3}, \quad 52\equiv 2\pmod{5}\quad \text{ y } \quad 52\equiv 3\pmod{7}.\]

El siguiente teorema nos va a proveer de un algoritmo para encontrar la solución de un sistema de congruencias de la forma \(x\equiv a_i\pmod{m_i}\), para \(i = 1,2, \ldots ,k\).

Teorema 50 (Teorema chino del residuo)

El sistema lineal de congruencias

\[\begin{split}\begin{cases} x\equiv a_1\pmod{m_1}, \\ & \\ x\equiv a_2\pmod{m_2}, \\ & \\ x\equiv a_3\pmod{m_3}, \\ \quad \vdots \\ x\equiv a_k\pmod{m_k}, \end{cases}\end{split}\]

en donde los módulo \(m_i\) son primos relativos por pares, para \(1\le i \le k,\) tiene solución y es única módulo \(m_1m_2m_3\cdot \ldots \cdot m_k\).

Demostración. \(\quad\)

• Primero vamos a construir la solución del sistema de congruencias.

Sea \(M = m_1m_2m_3\cdot \ldots \cdot m_k\) y \(M_i = \frac{M}{m_i}\), para cada \(1\le i \le k\). Como tenemos que \((m_i,m_j) = 1\), cuando \(i \neq j\), para \(1\le j \le k\) sucede que \((M_i, m_i) = 1\) para cada \(i\). Además, se cumple que \(M_i\equiv 0 \pmod{m_j}\) cuando \(i\neq j\).

Ya que \((M_i,m_i) = 1\), entonces por el Corolario 10 sabemos que la congruencia \(M_iy_i\equiv 1 \pmod{m_i}\) tiene una única solución \(y_i\).

Sea

\[x = a_1M_1y_1 + a_2M_2y_2 + a_3M_3y_3 + \ldots + a_kM_ky_k.\]

Ahora veamos que \(x\) es solución del sistema lineal de congruencias. Tenemos que

\[\begin{align*} x &= \sum_{i = 1}^{k}a_iM_iy_i \\ & \\ &= \sum_{i = 1, i\neq j}^{k}a_iM_iy_i + a_jM_jy_j \\ & \\ &\equiv \sum_{i\neq j}a_i\cdot 0 \cdot y_i + a_j\cdot 1 \pmod{m_j} \\ & \\ &\equiv a_j \pmod{m_j}, \end{align*}\]

lo anterior se cumple para cada \(1\le j\le k\), es decir, \(x\) satisface a todas las congruencias del sistema y por lo tanto es una solución.

• Ahora probemos que la solución es única módulo \(M\).

Sean \(x_0\) y \(x_1\) dos soluciones diferentes del sistema de congruencias, mostraremos que \(x_0\equiv x_1 \pmod{M}\).

Como tenemos que \(x_0\equiv a_j\pmod{m_j}\) y \(x_1\equiv a_j\pmod{m_j}\) para \(1\le j \le k\), entonces por la propiedad \(3\) del Teorema 29 tenemos que

\[\begin{align*} x_1 &\equiv x_0 \pmod{m_j} \\ & \\ x_1 - x_0 &\equiv 0\pmod{m_j}. \end{align*}\]

Lo anterior quiere decir que \(m_j|(x_1 - x_0)\) para toda \(j\). Luego, por el Corolario 11 tendríamos que \([m_1, m_2, \ldots ,m_k]|(x_1 - x_0)\). Pero por el Corolario 13, como los \(m_j\) son primos relativos por pares, tenemos que \([m_1,m_2, \ldots, m_k] = M\).
Por lo tanto, tenemos que \(M|(x_1 - x_0)\), lo cual quiere decir que \(x_1\equiv x_0 \pmod{M}\). Y así, cualquier par de soluciones del sistema lineal de congruencias son congruentes módulo \(M\). Por lo tanto la solución es única módulo \(M\). \(\square\)

Veamos un ejemplo en donde usamos el Teorema 50 para resolver un sistema de congruencias lineales.

Ejemplo 123

Encuentra el valor de \(x\) que satisface las siguientes congruencias, usando el teorema chino del residuo.

\[\begin{split}\begin{cases} x\equiv 1\pmod{3}, \\ & \\ x\equiv 3\pmod{4}, \\ & \\ x\equiv 4\pmod{7}, \\ & \\ x\equiv 7\pmod{11}. \end{cases}\end{split}\]

Solución.

Primero notemos que \(m_1 = 3, m_2 = 4, m_3 = 7\) y \(m_4 = 11\) son primos relativos por pares. Entonces podemos usar el teorema chino del residuo y sabemos que el sistema tiene solución única.

Vamos a calcular los valores de \(M_i = \frac{M}{m_i}\). Teniendo \(M = 3\cdot 4\cdot 7\cdot 11\), obtenemos que

\[\begin{align*} M_1 &= \frac{3\cdot 4\cdot 7\cdot 11}{3} = 4\cdot 7\cdot 11 = 308, \\ & \\ M_2 &= \frac{3\cdot 4\cdot 7\cdot 11}{4} = 3\cdot 7\cdot 11 = 231, \\ & \\ M_3 &= \frac{3\cdot 4\cdot 7\cdot 11}{7} = 3\cdot 4\cdot 11 = 132, \\ & \\ M_4 &= \frac{3\cdot 4\cdot 7\cdot 11}{11} = 3\cdot 4\cdot 7 = 84. \\ \end{align*}\]

Ahora vamos a encontrar los valores de \(y_i\) para \(i = 1,2,3,4\). Tenemos que resolver las congruencias \(M_iy_i\equiv 1\pmod{m_i}\).
Primero encontremos \(y_1.\)

\[\begin{align*} 308y_1 &\equiv 1 \pmod{3}, \\ & \\ 2y_1 &\equiv 1\pmod{3}, \\ & \\ 2\cdot 2y_1 &\equiv 2\cdot 1\pmod{3}, \\ & \\ y_1 &\equiv 2 \pmod{3}. \end{align*}\]

Encontremos el valor de \(y_2\).

\[\begin{align*} 231y_2 &\equiv 1 \pmod{4}, \\ & \\ 3y_2 &\equiv 1\pmod{4}, \\ & \\ 3\cdot 3y_2 &\equiv 3\cdot 1\pmod{4}, \\ & \\ y_2 &\equiv 3 \pmod{4}. \end{align*}\]

Busquemos el valor de \(y_3\).

\[\begin{align*} 132y_3 &\equiv 1 \pmod{7}, \\ & \\ 6y_3 &\equiv 1\pmod{7}, \\ & \\ 6\cdot 6y_3 &\equiv 6\cdot 1\pmod{7}, \\ & \\ y_3 &\equiv 6 \pmod{7}. \end{align*}\]

Finalmente encontremos \(y_4\).

\[\begin{align*} 84y_4 &\equiv 1 \pmod{11}, \\ & \\ 7y_4 &\equiv 1\pmod{11}, \\ & \\ 8\cdot 7y_4 &\equiv 8\cdot 1\pmod{11}, \\ & \\ y_4 &\equiv 8 \pmod{11}. \end{align*}\]

Por lo tanto \(y_1 = 2, y_2 = 3, y_3 = 6\) y \(y_4 = 8\).

Ahora vamos a construir la solución \(x\).

\[\begin{align*} x &\equiv \sum_{i=1}^{4} a_iM_iy_i \pmod{M} \\ & \\ &\equiv 1\cdot 308\cdot 2 + 3\cdot 231\cdot 3 + 4\cdot 132\cdot 6 + 7\cdot 84 \cdot 8 \pmod{924}\\ & \\ &\equiv 616 + 2079 + 3168 + 4704 \pmod{924} \\ & \\ &\equiv 10567 \pmod{924} \\ & \\ &\equiv 403 \pmod{924}. \end{align*}\]

Por lo tanto la solución única es \(x = 403\).

Aplicaciones del teorema chino del residuo

Ejemplo 124

Supongamos ahora que tenemos una calculadora en donde el número más grande que puede mostrar es el \(99,999,999\) y queremos calcular el valor exacto de \(2^{31}\).

Usando el teorema chino del residuo podemos calcular el valor de \(x = 2^{31}\). Primero vamos a seleccionar \(k\) enteros que sean primos relativos por pares, es decir seleccionaremos \(m_1, m_2, \ldots ,m_k\), en donde \(M = m_1m_2\cdot \ldots \cdot m_k\). Después calcularemos el residuo mínimo \(r\) de \(x\) módulo \(M\). Ya que \(x\equiv r\pmod{M}\) y \(0<r<M\), \(r\) será el valor exacto de \(x\).

La potencia de \(2\) más grande que puede mostrar nuestra calculadora es \(2^{26} = 67,108,864\) mientras que \(2^{31} \approx 2.1474836 \times 10^9\). Entonces vamos a seleccionar \(m_1 = 300, m_2 = 301, m_3 = 307\) y \(m_4 = 311\), los cuales son primos relativos por pares. Además, \(M = m_1m_2m_3m_4 = 300\cdot 301\cdot 307\cdot 311 > x\). Para revisar esto veamos que

\[\begin{align*} M = 300\cdot 301\cdot 307\cdot 311 &> 300\cdot 300\cdot 300\cdot 300 \\ & \\ &= (3\times 10^2)\cdot (3\times 10^2)\cdot (3\times 10^2)\cdot (3\times 10^2) \\ & \\ &= 3^4\times 10^8 \\ & \\ &> 81\times 10^8 \\ & \\ &> 8\times 10^9. \end{align*}\]

Por lo tanto \(M > x\). No necesitamos saber el valor exacto de \(M\), sólo asegurar que sea más grande que \(x\).

Ya que \(2^{31} = 2\cdot 2^{10}\cdot 2^{10}\cdot 2^{10}\), vamos a calcular de esta manera \(2^{31}\equiv x_i\pmod{m_i}\).
Primero vamos a calcular \(2^{10} = 1024\) módulo \(m_i\) para \(i = 1,2,3,4\). Tenemos que

\[\begin{align*} 1024 &\equiv 124\pmod{300}, \\ & \\ 1024 &\equiv 121\pmod{301}, \\ & \\ 1024 &\equiv 103\pmod{307}, \\ & \\ 1024 &\equiv 91\pmod{311}. \\ \end{align*}\]

Ahora vamos a calcular \(2^{31}\equiv x_i\pmod{m_i}\).

\[\begin{align*} 2^{31} &\equiv 2\cdot 2^{10}\cdot 2^{10}\cdot 2^{10} \equiv 2\cdot 124\cdot 124\cdot 124 \equiv 3813248\equiv -52\pmod{300}, \\ & \\ 2^{31} &\equiv 2\cdot 2^{10}\cdot 2^{10}\cdot 2^{10} \equiv 2\cdot 121\cdot 121\cdot 121 \equiv 3543122\equiv 51\pmod{301}, \\ & \\ 2^{31} &\equiv 2\cdot 2^{10}\cdot 2^{10}\cdot 2^{10} \equiv 2\cdot 103\cdot 103\cdot 103 \equiv 2185454\equiv 228\pmod{307}, \\ & \\ 2^{31} &\equiv 2\cdot 2^{10}\cdot 2^{10}\cdot 2^{10} \equiv 2\cdot 91\cdot 91\cdot 91\equiv 1507142\equiv 36\pmod{300}. \\ \end{align*}\]

Entonces tenemos el siguiente sistema de congruencias.

\[\begin{split}\begin{cases} x \equiv -52\pmod{300}, \\ & \\ x \equiv 51\pmod{301}, \\ & \\ x \equiv 228\pmod{307}, \\ & \\ x \equiv 36\pmod{311}. \end{cases}\end{split}\]

Ahora vamos a calcular \(M_i = \frac{M}{m_i}\).

\[\begin{align*} M_1 &= \frac{M}{m_1} = \frac{300\cdot 301\cdot 307\cdot 311}{300} = 301\cdot 307\cdot 311, \\ & \\ M_2 &= \frac{M}{m_2} = \frac{300\cdot 301\cdot 307\cdot 311}{301} = 300\cdot 307\cdot 311, \\ & \\ M_3 &= \frac{M}{m_3} = \frac{300\cdot 301\cdot 307\cdot 311}{307} = 300\cdot 301\cdot 311, \\ & \\ M_4 &= \frac{M}{m_4} = \frac{300\cdot 301\cdot 307\cdot 311}{311} = 300\cdot 301\cdot 307. \\ \end{align*}\]

Ahora vamos a calcular los valores de \(y_1, y_2, y_3\) y \(y_4\), resolviendo las congruencias \(M_iy_i\equiv 1\pmod{m_i}\).
Encontremos \(y_1\).

\[\begin{align*} 301\cdot 307\cdot 311y_1 &\equiv 1\pmod{300}, \\ & \\ 1\cdot 7\cdot 11y_1 &\equiv 1\pmod{300}, \\ & \\ 77y_1 &\equiv 1\pmod{300}, \\ & \\ 113\cdot 77y_1 &\equiv 113\cdot 1\pmod{300}, \\ & \\ y_1 &\equiv 113\pmod{300}. \end{align*}\]

Encontremos \(y_2\).

\[\begin{align*} 300\cdot 307\cdot 311y_2 &\equiv 1\pmod{301}, \\ & \\ (-1)\cdot 6\cdot 10y_2 &\equiv 1\pmod{301}, \\ & \\ -60y_2 &\equiv 1\pmod{301}, \\ & \\ 5\cdot (-60)y_2 &\equiv 5\cdot 1\pmod{301}, \\ & \\ y_2 &\equiv 5\pmod{301}. \end{align*}\]

Encontremos \(y_3\).

\[\begin{align*} 300\cdot 301\cdot 311y_3 &\equiv 1\pmod{307}, \\ & \\ (-7)\cdot (-6)\cdot 4y_3 &\equiv 1\pmod{307}, \\ & \\ 168y_3 &\equiv 1\pmod{307}, \\ & \\ 53\cdot 168y_3 &\equiv 53\cdot 1\pmod{307}, \\ & \\ y_3 &\equiv 53\pmod{307}. \end{align*}\]

Encontremos \(y_4\).

\[\begin{align*} 300\cdot 301\cdot 307y_4 &\equiv 1\pmod{311}, \\ & \\ (-11)\cdot (-10)\cdot (-4)y_4 &\equiv 1\pmod{311}, \\ & \\ -440y_4 &\equiv 1\pmod{311}, \\ & \\ 182y_4 &\equiv 1\pmod{311}, \\ & \\ 135\cdot 182y_4 &\equiv 135\cdot 1\pmod{311}, \\ & \\ y_4 &\equiv 135\pmod{311}. \end{align*}\]

Entonces \(y_1 = 113, y_2 = 5, y_3 = 53\) y \(y_4 = 135\).

Ahora, vamos a construir la solución \(x = \sum_{i=1}^{4}a_iM_iy_i \pmod{M}\).

\[\begin{align*} x &\equiv \sum_{i=1}^{4}a_iM_iy_i \pmod{M} \\ & \\ &\equiv a_1M_1y_1 + a_2M_2y_2 + a_3M_3y_3 + a_4M_4y_4 \\ & \\ &\equiv (-52)\cdot 301\cdot 307\cdot 311\cdot 113 + 51\cdot 300\cdot 307\cdot 311\cdot 5 \\ & + 228\cdot 300\cdot 301\cdot 311\cdot 53 + 36\cdot 300\cdot 301\cdot 307\cdot 135 \pmod{M} \end{align*}\]

Ahora, para poder calcular esta cuenta, podemos reducir un poco los términos. Usaremos el Lema 12 para reducir estas cuentas.
Notemos lo siguiente para el primer sumando

\[(-52)\cdot 113 \equiv -5876 \equiv 124 \pmod{300}.\]

Esta congruencia podemos multiplicarla por \(301\cdot 307\cdot 311\) y tendríamos que

\[(-52)\cdot 301\cdot 307\cdot 311\cdot 113 \equiv 124\cdot 301\cdot 307\cdot 311 \pmod{M}.\]

Vamos a realizar lo mismo con los siguientes términos de la suma, la idea es poder realizar las operaciones con nuestra calculadora de \(8\) cifras. Entonces tendríamos lo siguiente. Para el segundo sumando tendríamos,

\[\begin{align*} 51\cdot 5 &\equiv -46\pmod{301}, \\ & \\ 51\cdot 300\cdot 307\cdot 311\cdot 5 &\equiv -46\cdot 300\cdot 307\cdot 311 \pmod{M}. \end{align*}\]

Para el tercer sumando tendríamos,

\[\begin{align*} 228\cdot 53 &\equiv 111\pmod{307}, \\ & \\ 228\cdot 300\cdot 301\cdot 311\cdot 53 &\equiv 111\cdot 300\cdot 301\cdot 311 \pmod{M}. \end{align*}\]

Y para el cuarto sumando,

\[\begin{align*} 36\cdot 135 &\equiv -116\pmod{311}, \\ & \\ 36\cdot 300\cdot 301\cdot 307\cdot 135 &\equiv -116\cdot 300\cdot 301\cdot 307\pmod{M}. \end{align*}\]

Entonces tendríamos que

\[\begin{align*} x &\equiv 124\cdot 301\cdot 307\cdot 311 -46\cdot 300\cdot 307\cdot 311 \\ &\quad + 111\cdot 300\cdot 301\cdot 311 -116\cdot 300\cdot 301\cdot 307\pmod{M} \\ & \\ &\equiv (124\cdot 301 - 46\cdot 300)\cdot 307\cdot 311 + (111\cdot 311 - 116\cdot307)\cdot 300\cdot 301 \pmod{M} \\ & \\ &\equiv (37324 - 13800)\cdot 307\cdot 311 + (34521 - 35612)\cdot 300\cdot 301 \pmod{M} \\ & \\ &\equiv (23524)\cdot 307\cdot 311 + (-1091)\cdot 300\cdot 301 \pmod{M} \\ & \\ &\equiv (23000)\cdot 307\cdot 311 + (524)\cdot 307\cdot 311 - 1091\cdot 300\cdot 301 \pmod{M} \quad \text{(aprovechando los ceros, nos ahorramos dígitos.)} \\ & \\ &\equiv 2195971000 + 50029948 - 98517300 \pmod{M} \\ & \\ &\equiv 2147483648\pmod{M}. \end{align*}\]

Por lo tanto \(2^{31} = 2147483648\).

Por último veamos el siguiente ejercicio, es cual nos muestra que podemos resolver una congruencia lineal, partiendo el problema en un sistema de congruencias. Se dejará como ejercicio de práctica demostrar el teorema que nos permite realizar el siguiente ejercicio.

Ejemplo 125

Resuelve la congruencia \(91x\equiv 419\pmod{440}\).

Solución.

Ya sabemos resolver este tipo de congruencias, pero en lugar de usar el algoritmo visto en la sección de congruencias lineales vamos a aprovechar el teorema chino del residuo para descomponer la congruencias en un sistema de congruencias.

Primero notemos que \(440 = 2^3\cdot 5\cdot 11\), entonces podemos descomponer la congruencia en el siguiente sistema de congruencias:

\[\begin{split}\begin{cases} 91x \equiv 419\pmod{5}, \\ & \\ 91x \equiv 419\pmod{8}, \\ & \\ 91x \equiv 419\pmod{11}. \end{cases}\end{split}\]

El sistema anterior lo podemos simplificar y tendríamos que

\[\begin{split}\begin{cases} x \equiv 4\pmod{5}, \\ & \\ 3x \equiv 3\pmod{8}, \\ & \\ 3x \equiv 1\pmod{11}. \end{cases}\end{split}\]

Ahora, para la segunda congruencia, tendríamos que como \((3,8) = 1\) el inverso de \(3\) sería \(3\) ya que \(3\cdot 3 = 9 \equiv 1\pmod{8}\). Entonces multiplicaríamos la congruencia por \(3\) y obtendríamos que

\[\begin{align*} 3x &\equiv 3\pmod{8}, \\ & \\ 3\cdot 3x &\equiv 3\cdot 3\pmod{8}, \\ & \\ x &\equiv 1\pmod{8}. \end{align*}\]

Luego para la tercera congruencia tendríamos que \((3,11) = 1\) y así el inverso de \(3\) módulo \(11\) sería \(4\) ya que \(4\cdot 3 = 12 \equiv 1\pmod{11}\). Entonces, si multiplicamos la congruencia por \(4\) tendríamos que

\[\begin{align*} 3x &\equiv 1\pmod{11}, \\ & \\ 4\cdot 3x &\equiv 4\cdot 1\pmod{11}, \\ & \\ x &\equiv 4\pmod{11}. \end{align*}\]

Por lo tanto, el sistema que nos queda a resolver sería

\[\begin{split}\begin{cases} x\equiv 4\pmod{5}, \\ & \\ x\equiv 1\pmod{8}, \\ & \\ x\equiv 4\pmod{11}. \end{cases}\end{split}\]

Notemos lo siguiente \((5,8) = (8,11) = (11,5) = 1\), es decir que los módulos son primos relativos por pares. Por lo tanto, podemos aplicar el teorema chino del residuo.

Calculemos el valor de \(M_i = \frac{M}{m_i}\).

\[\begin{align*} M_1 &= \frac{5\cdot 8\cdot 11}{5} = 88, \\ & \\ M_2 &= \frac{5\cdot 8\cdot 11}{8} = 55, \\ & \\ M_3 &= \frac{5\cdot 8\cdot 11}{11} = 40. \\ & \\ \end{align*}\]

Ahora, calculemos los valores de \(y_i\) resolviendo la congruencia \(M_iy_i\equiv 1\pmod{m_i}\).

Primero encontremos \(y_1\).

\[\begin{align*} 88y_1 &\equiv 1\pmod{5}, \\ & \\ 3y_1 &\equiv 1\pmod{5}, \\ & \\ y_1 &\equiv 2\pmod{5}. \end{align*}\]

Encontremos \(y_2\).

\[\begin{align*} 55y_2 &\equiv 1\pmod{8}, \\ & \\ 7y_2 &\equiv 1\pmod{8}, \\ & \\ y_2 &\equiv 7\pmod{5}. \end{align*}\]

Por último, calculemos \(y_3\).

\[\begin{align*} 40y_3 &\equiv 1\pmod{11}, \\ & \\ 7y_3 &\equiv 1\pmod{11}, \\ & \\ y_3 &\equiv 8\pmod{11}. \end{align*}\]

Ahora calculemos la solución, \(x \equiv \sum_{i = 1}^{3} a_iM_iy_i \pmod{M}\).

\[\begin{align*} x &\equiv \sum_{i = 1}^{3} a_iM_iy_i \pmod{440} \\ & \\ &\equiv 4\cdot 88\cdot 2 + 1\cdot 55\cdot 7 + 4\cdot 40\cdot 8 \pmod{440} \\ & \\ &\equiv 704 + 385 + 1280 \pmod{440}\\ & \\ &\equiv 2369 \pmod{440} \\ & \\ &\equiv 169 \pmod{440}. \end{align*}\]

Por lo tanto la solución es \(x = 169\) y podemos comprobar que \(91 \cdot 169 = 15379\equiv 419\pmod{440}\).

Código para el teorema chino del residuo

En esta sección vamos a escribir un código que nos ayudará a resolver sistemas de congruencias de la forma \(x\equiv a_i\pmod{m_i}\), en donde los valores de \(m_i\) deben de ser primos relativos por pares para poder aplicar el teorema chino del residuo.
Ocuparemos el código construido en la sección del algoritmo de Euclides para encontrar el máximo común divisor de dos números y la función para calcular el inverso de un número módulo \(m\) construida en la sección de congruencias y propiedades básicas.

def euclides_extendido_ciclos(a,b):
    s=[1,0]
    t=[0,1]
    while b!=0:
        q=a//b
        r=a%b
        nuevo_s=s[-2]-q*s[-1]
        nuevo_t=t[-2]-q*t[-1]
        s.append(nuevo_s)
        t.append(nuevo_t)
        a,b=b,r
    return s[-2],t[-2],a

def inverso_modn(a,m):  
    alfa,beta,d = euclides_extendido_ciclos(a,m)    
    if d == 1:
        return alfa

La siguiente función nos ayuda a verificar si los números en una lista son primos relativos por pares.

def p_relativos_pares(lista):
    for i in range(len(lista)):
        for j in range(i+1, len(lista)):
            x,y,z = euclides_extendido_ciclos(lista[i], lista[j])
            if z != 1:
                return False
    return True 

lista = [5,7,11,28,19,23]

p_relativos_pares(lista)

False

lista = [5,7,11,19,23]

p_relativos_pares(lista)

True

El siguiente código nos ayuda a resolver el sistema de congruencias lineales con el teorema chino del residuo. Recibe como argumento una lista de parejas ordenadas

\[\text{lista} = [(a_1,m_1), (a_2,m_2), \ldots (a_k,m_k) ],\]

las cuales toman los valores de las congruencias \(x\equiv a_i\pmod{m_i}\).

def congr_thm_chi(lista):
    lista_a_i = []
    lista_m_i = []
    for i in range(len(lista)):
        lista_a_i.append(lista[i][0])
        lista_m_i.append(lista[i][1])

    if p_relativos_pares(lista_m_i) == True:
        M = 1
        for m in lista_m_i:
            M *= m
        lista_M_i = [M//x for x in lista_m_i]
        lista_y_i = [inverso_modn(lista_M_i[i],lista_m_i[i]) for i in range(len(lista))]
        x = 0
        for i in range(len(lista)):
            x += lista_a_i[i]*lista_M_i[i]*lista_y_i[i]
        return print(f"La solución del sistema de congruencias es {x%M}")         
    else:
        return print("Los módulos no son primos relativos por pares.")

congr_thm_chi([(1,3),(2,4),(3,5)])

La solución del sistema de congruencias es 58

congr_thm_chi([(-52,300),(51,301),(228,307),(36,311)])

La solución del sistema de congruencias es 2147483648

congr_thm_chi([(65,99),(2,98),(51,97),(10,95)])

La solución del sistema de congruencias es 537140

Explicación del código

En esta ocasión reutilizamos códigos creados en secciones anteriores, pero los modificamos. Mostraremos los códigos originales y la modificación que se les hizo.

Código original.

def inverso_modn(a,m):  
    alfa,beta,d = euclides_extendido_ciclos(a,m)    
    if d == 1:
        print(f"El inverso de {a} es {alfa}, es decir que, {a}x{alfa} ≡ 1 (mod{m})")
    else:  
        print(f"({a},{m}) es diferente de 1, entonces {a} no tiene inverso módulo {m}")

Código modificado.

def inverso_modn(a,m):  
    alfa,beta,d = euclides_extendido_ciclos(a,m)    
    if d == 1:
        return alfa

Para este código eliminamos el condicional else, haciendo que la función solo nos regrese el valor del inverso de \(a\) módulo \(m\). Esto debido a que en el código que usamos para resolver el sistema de congruencias, primero verificamos si los módulos son primos relativos. De ser cierto, entonces el teorema chino del residuo no asegura encontrar la solución y existirían los inversos de los valores \(M_i\).

Ahora, vamos a ver la función que creamos para verificar que los enteros contenidos en una lista son primos relativos por pares. Veamos cómo funciona este código.

def p_relativos_pares(lista):
    for i in range(len(lista)):
        for j in range(i+1,len(lista)):          
            if algoritmo_euclides(lista[i],lista[j]) != 1:
                return False
    return True

1. Definimos una función llamada «p_relativos_pares» la cual recibe como argumento una lista de números enteros.

def p_relativos_pares(lista):

2. Luego comenzamos un ciclo for el cual va a ir tomando los elementos de la lista. A este le sigue otro ciclo for que va a ir tomando los elementos siguientes del elemento elegido en el anterior ciclo for. Es decir, si tuviéramos una lista de \(n\) elementos \(l = [a_1,a_2,a_3, \ldots, a_n]\), si el primer ciclo for toma el elemento \(a_i\) para \(i = 1,2,\ldots ,n\), el siguiente ciclo for tomará los elementos \(a_j\) para \(j =i+1, i+2, i+3,\ldots , i + (n - i)\). Luego, cuando ya se elijen dos valores, tenemos un condicional if el cual revisa si el máximo común divisor entre \(a_i\) y \(a_j\) es igual a \(1\). Si esto es cierto, el ciclo se repite hasta revisar todas las parejas y nos da como resulta un valor booleano de True. Si es falso el código se detiene y nos arroja un valor de False.

    for i in range(len(lista)):
        for j in range(i+1,len(lista)):          
            if algoritmo_euclides(lista[i],lista[j]) != 1:
                return False
    return True

Por último vamos a explicar el código que nos ayuda a resolver el sistema de congruencias \(x\equiv a_i\pmod{m_i}\).

def congr_thm_chi(lista):
    lista_a_i = []
    lista_m_i = []
    for i in range(len(lista)):
        lista_a_i.append(lista[i][0])
        lista_m_i.append(lista[i][1])

    if p_relativos_pares(lista_m_i) == True:
        M = 1
        for m in lista_m_i:
            M *= m
        lista_M_i = [M//x for x in lista_m_i]
        lista_y_i = [inverso_modn(lista_M_i[i],lista_m_i[i]) for i in range(len(lista_m_i))]
        x = 0
        for i in range(len(lista)):
            x += lista_a_i[i]*lista_M_i[i]*lista_y_i[i]
        return print(f"La solución del sistema de congruencias es {x%M}")         
    else:
        return print("Los módulos no son primos relativos por pares.")

1. Definimos una función llamada «congr_thm_chi» la cual recibe como argumento una lista con las parejas ordenadas \((a_i,m_i)\), los cuales son los coeficientes y módulos de las congruencias \(x\equiv a_i\pmod{m_i}\).
   Creamos dos variables «lista_a_i» y «lista_m_i» las cuales son listas vacías. Empezamos un ciclo for el cual va tomando las parejas ordenadas \((a_i,m_i)\) de la lista. Lo que sucede a continuación es que el valor \(a_i\) se guarda en la lista «lista_a_i» y el valor de \(m_i\) se guarda en la lista «lista_m_i». Con esto logramos separar los valores, pero aunque estén en diferente lista los valores de la \(i\)-ésima congruencia se identifican con el \((i-1)\)-ésimo índice de la lista.

def congr_thm_chi(lista):
    lista_a_i = []
    lista_m_i = []
    for i in range(len(lista)):
        lista_a_i.append(lista[i][0])
        lista_m_i.append(lista[i][1])

2. Para que se pueda usar el algoritmo del teorema chino del residuo, necesitamos verificar que los módulos de las congruencias sean primos relativos por pares. Esto lo hacemos con un condicional if, el cual verifica que la función «p_relativos_pares» arroje como valor True.

    if p_relativos_pares(lista_m_i) == True:

3. Si el condicional arroja un valor de True entonces el código pasa a calcular los valores de \(M_i\) y \(y_i\). Empezamos calculando el valor de \(M = m_1m_2m_3\cdot \ldots \cdot m_n\).
   Creamos una variable «M» con un valor inicial de \(1\), luego con un ciclo for recorremos los valores de la lista «lista_m_i» y cada valor se va multiplicando a la variable «M» hasta obtener la multiplicación de todos.
   Ahora, necesitamos encontrar los valores de \(M_i\) para poder resolver las congruencias \(M_iy_i\equiv 1\pmod{m_i}\) y así poder obtener los valores de cada \(y_i\).
   Creamos una lista llamada «lista_M_i» la cual se construye con una compresión de lista. Recordemos que \(M_i = \frac{M}{m_i}\), entonces la expresión que usamos para crear la lista es M//x y con un ciclo for vamos tomando los valores de la lista «lista_m_i» y se van dividiendo entre el valor «M».
   También creamos una lista llamada «lista_y_i», la cual guardará los valores de cada \(y_i\), los cuales se obtienen calculando el inverso de \(M_i\) módulo \(m_i\). En este caso la expresión que usamos es la función que construimos para calcular inversos. Como argumento le pasamos los valores de \(M_i\) y el módulo \(m_i\). Con esto lo que obtenemos son los valores de \(y_i\). Nuevamente aunque estén en diferentes listas los valores de la \(i\)-ésima congruencia se identifican con el \((i-1)\)-ésimo índice de la lista.

        M = 1
        for m in lista_m_i:
            M *= m
        lista_M_i = [M//x for x in lista_m_i]
        lista_y_i = [inverso_modn(lista_M_i[i],lista_m_i[i]) for i in range(len(lista_m_i))]

4. Ahora lo que tenemos que calcular es el valor de la solución, el cual es \(x = \sum_{i=1}^{n}a_im_iy_i\). Entonces creamos una variable «x» que comienza con un valor de cero. Enseguida creamos un ciclo for el cual tiene como rango para recorrer desde \(0\) hasta \(n-1\). Este ciclo toma los valores de las listas «lista_a_i», «lista_M_i» y «lista_y_i», estos valores se multiplican y se van sumando a la variable «x». Finalmente nos arroja la solución del sistema de congruencias módulo \(M\).

        x = 0
        for i in range(len(lista)):
            x += lista_a_i[i]*lista_M_i[i]*lista_y_i[i]
        return print(f"La solución del sistema de congruencias es {x%M}")

5. La condición else, la cual se ejecuta si los módulos no son primos relativos por pares. Entonces el código nos imprime un mensaje en donde nos dice que los módulos no son primos relativos por pares.

    else:
        return print("Los módulos no son primos relativos por pares.")

Ejercicios de práctica

1. Resuelve lo siguiente.

   • ¿Qué enteros dejan un residuo de \(1\) cuando son divididos tanto, entre \(2\) como entre \(3\)?

   • Encuentra un entero que deje residuo de \(1\) cuando es dividido por \(2\) o por \(5\), pero que sea divisible entre \(3\).

2. Demuestra que si \(x_1\) y \(x_2\) son soluciones del sistema visto en el Teorema 49, entonces \(x_1\equiv x_2\pmod{mn}\), es decir que la solución es única módulo \(mn\).

3. Encuentra el valor de \(x\) que satisface los siguientes sistemas de congruencias.

   • \(x\equiv 2\pmod{3}, x\equiv 4\pmod{5}\) y \(x\equiv 5\pmod{7}\).

   • \(x\equiv 0\pmod{2}, x\equiv 0\pmod{3}, x\equiv 1\pmod{5}\) y \(x\equiv 6\pmod{7}\).

   • \(x\equiv 2\pmod{11}, x\equiv 2\pmod{12}, x\equiv 4\pmod{13}, x\equiv 5\pmod{17}\) y \(x\equiv 6\pmod{19}\).

4. Encuentra el menor entero positivo \(n\) tal que \(2|n, 3|(n+1), 5|(n+2), 7|(n+3)\) y \(11|(n+4)\).

5. Demuestra que si \(n = p_1^{e_1}p_2^{e_2}\cdot \ldots \cdot p_k^{e_k}\), en donde \(p_1,p_2,\ldots ,p_k\) son primos distintos, entonces para cualesquiera enteros \(a\) y \(b\) tenemos que \(a\equiv b\pmod{n}\) si y sólo si \(a\equiv b\pmod{p_i^{e_i}}\) para cada \(i = 1,2,\ldots ,k\).