[skip-to-content]

Sección 3.8 Teorema Chino del Resto

La motivación para introducir esta sección es la siguiente: ¿Es posible descomponer \(119x \equiv 35\) (mod \(1001\)) en expresiones más sencillas para poder encontrar las soluciones correspondientes de la ecuación original?

Adicionalmente, ¿existirá algún número entero \(x\) que satisfaga simultaneamente las ecuaciones:

\begin{equation*} x\equiv 1 \ (\text{mod } {5}), x\equiv 2 \ (\text{mod } {6}), x\equiv 3 \ (\text{mod } {7})\text{?} \end{equation*}

Estas interrogantes pueden resolverse gracias al Teorema Chino del Resto.

Definición 3.8.1.
(Sistema Lineal de Congruencia) Sean \(a_{i}, b_{i} \in \mathbb{Z}\) y \(n_{i}\in \mathbb{N}\) con \(i=1,2,...,r\text{.}\) Se denomina Sistema Lineal de Congruencia al conjunto de ecuaciones
\begin{align*} a_{1}x \amp \equiv b_{1} \ (\text{mod } n_{1})\\ a_{2}x \amp \equiv b_{2} \ (\text{mod } n_{2})\\ a_{3}x \amp \equiv b_{3} \ (\text{mod } n_{3})\\ \vdots\\ a_{r}x \amp \equiv b_{r} \ (\text{mod } n_{r}) \end{align*}

Se dice que \(x\) es solución del sistema lineal de congruencia si satisface simultaneamente todas las ecuaciones involucradas.

La siguiente proposición es muy útil para verificar cuando un sistema lineal de congruencia (compuesto de dos ecuaciones) tiene solución. Puede ser aplicado astutamente en un sistema lineal de congruencia compuesto por \(n\) ecuaciones (Ver Ejemplos 3.8.3 y 3.8.4).

Supondremos que el sistema es soluble y admite a \(x_{0}\) como solución. Por lo tanto, existen números enteros \(h,t\) tales que
\begin{equation*} x_{0}=a_{1}+n_{1}h \end{equation*}
\begin{equation*} x_{0}=a_{2}+n_{2}t\text{.} \end{equation*}
Por consiguiente,
\begin{equation*} a_{1}+n_{1}h=a_{2}+n_{2}t\text{.} \end{equation*}
Así, \(a_{1}-a_{2}=n_{2}t-n_{1}h\text{.}\) Como \((n_{1},n_{2})|n_{1}\) y \((n_{1},n_{2})|n_{2}\text{,}\) entonces \((n_{1},n_{2})|(xn_{1}+yn_{2})\) para todo \(x,y \in \mathbb{Z}\text{.}\) Basta tomar \(y=t\) y \(x=-h\) para conseguir \((n_{1},n_{2})|(n_{2}t-n_{1}h)\text{.}\) De esta manera, \((n_{1},n_{2})|(a_{1}-a_{2}).\)

Por otro lado, sea \(d=(n_{1},n_{2})\) Por Bézout, existen enteros \(x,y\) tales que

\begin{equation*} xn_{1}+yn_{2}=d\text{.} \end{equation*}
Adicionalmente, por hipótesis es sabido que \(d|(a_{1}-a_{2})\text{.}\) Por lo tanto, existe un único entero \(l\) tal que \(dl=a_{1}-a_{2}\text{.}\) Multiplicando por \(l\) en la combinación lineal entera (obtenida por Bézout); se logra
\begin{equation*} xn_{1}l+yn_{2}l=dl=a_{1}-a_{2}. \end{equation*}
Reordenando, se consigue \(a_{2}+yn_{2}l=a_{1}+(-x)n_{1}l \text{.}\) Esto equivale a que existe un entero \(z\text{,}\) tal que
\begin{equation*} z\equiv a_{1} \ (\text{mod } n_{1}) \end{equation*}
\begin{equation*} z\equiv a_{2} \ (\text{mod } n_{2}) \end{equation*}
Por lo tanto, el sistema tiene solución.
El sistema
\begin{align*} 2x \amp \equiv 4 \ (\text{mod } 8)\\ 7x \amp \equiv 19 \ (\text{mod } 6)\\ 2x \amp \equiv 14\ (\text{mod } 15) \end{align*}
no tiene solución. Para utilizar la Proposición 3.8.2, debemos simplificar el sistema. Calculando los inversos multiplicativos respectivos, se obtiene
\begin{align*} x \amp \equiv 2 \ (\text{mod } 4)\\ x \amp \equiv 1 \ (\text{mod } 6)\\ x \amp \equiv 7\ (\text{mod } 15) \end{align*}
Como el sistema está compuesto de tres ecuaciones, debemos analizar los casos
\begin{align*} x \amp \equiv 1 \ (\text{mod } 6)\\ x \amp \equiv 7\ (\text{mod } 15) \end{align*}
donde \((6,15)=3|(-6)\text{.}\) Adicionalmente
\begin{align*} x \amp \equiv 2 \ (\text{mod } 4)\\ x \amp \equiv 7\ (\text{mod } 15) \end{align*}
donde \((4,15)=1|(-5)\text{.}\) Sin embargo en
\begin{align*} x \amp \equiv 2 \ (\text{mod } 4)\\ x \amp \equiv 1\ (\text{mod } 6) \end{align*}
se tiene que \((4,6)=2\not\mid 1\text{.}\) Por lo tanto, el sistema no tiene solución (basta que solo un caso no cumpla lo estipulado por la Proposición 3.8.2 para concluir que el sistema no es soluble).
El sistema
\begin{align*} 168x \amp \equiv 24 \ (\text{mod } 220)\\ 56x \amp \equiv 40 \ (\text{mod } 68) \end{align*}
si tiene solución. Esto, dado que \((220,68)=4|(-16)\text{.}\) Por Proposición 3.8.2, el sistema es soluble.

Pero, ¿cómo encontrar la solución a un sistema lineal de congruencia? Es el momento de considerar el Teorema Chino del Resto.

La demostración de este teorema está compuesta de dos partes: verificar la existencia y unicidad para la solución.

Existencia: Considere \(N=n_{1}\cdot n_{2}\cdot ... \cdot n_{k}\) y \(c_{i}=\dfrac{N}{n_{i}}\text{,}\) para \(i=1,...,k\text{.}\) Dado que los módulos \(n_{i}\) son coprimos entre sí, \(c_{i}\) y \(n_{i}\) también lo son. Por consiguiente, \(\left(c_{i}, n_{i}\right)=1\text{.}\) Por Bézout, existen enteros \(d_{i},s_{i}\) tales que \(d_{i}c_{i}+s_{i}n_{i}=1\text{.}\) Trabajando esta expresión en módulo \(n_{i}\) y \(n_{j}\) (con \(i\neq j\)), se obtiene

\begin{align*} d_{i}\cdot c_{i} \amp \equiv 1 \ (\text{mod } n_{i})\\ d_{i}\cdot c_{i}\amp \equiv 1 \ (\text{mod } n_{i}) \end{align*}
Definiendo
\begin{equation*} x := \displaystyle\sum_{i=1}^k a_{i}\cdot c_{i} \cdot d_{i}, \end{equation*}
se consigue que \(x\) es la solución del sistema. Adicionalmente; trabajando en módulo \(n_{i}\text{,}\) se logra \(x \equiv a_{i} \ (\text{mod } n_{i})\) para todo \(i=1,...,k.\)

Unicidad: Supondremos que existen dos números enteros distintos \(x,y\) tales que

\begin{align*} x \amp \equiv a_{i} \ (\text{mod } n_{i})\\ y \amp \equiv a_{i} \ (\text{mod } n_{i}) \end{align*}
para todo \(i=1,...,k.\) Esto implica que \(x-y\equiv0 \ (\text{mod } n_{i}).\) Como todos los \(n_{i}\) son coprimos entre sí, entonces \(x-y\equiv0 \ (\text{mod } N).\) Es decir, \(x\equiv y \ (\text{mod } N).\) Por lo tanto, la solución debe ser única en módulo \(N\text{.}\)
El sistema
\begin{align*} x \amp \equiv 2 \ (\text{mod } 5)\\ 2x \amp \equiv 1 \ (\text{mod } 7)\\ 3x \amp \equiv 4\ (\text{mod } 11) \end{align*}
tiene solución (garantizada por el Teorema Chino del Resto, dado que los módulos involucrados son coprimos entre sí). Además
\begin{equation*} 2x \equiv 1 \ (\text{mod } 7)\Leftrightarrow x \equiv 4 \ (\text{mod } 7) \end{equation*}
\begin{equation*} 3x \equiv 4 \ (\text{mod } 11)\Leftrightarrow x \equiv 5 \ (\text{mod } 11)\text{.} \end{equation*}
Por lo tanto, obtenemos un sistema equivalente; tal que
\begin{align*} x \amp \equiv 2 \ (\text{mod } 5)\\ x \amp \equiv 4 \ (\text{mod } 7)\\ x \amp \equiv 5\ (\text{mod } 11) \end{align*}
La solución del sistema esta expresada en módulo
\begin{equation*} N=5\cdot 7 \cdot 11=385. \end{equation*}
Debemos encontrar los valores (enteros) de \(c_{1},c_{2}\) y \(c_{3}\) tales que
\begin{align*} c_{1} \amp = \dfrac{385}{5} = 77\\ c_{2} \amp = \dfrac{385}{7} = 55\\ c_{3} \amp = \dfrac{385}{11} = 35 \end{align*}
Con los valores de \(c_{1},c_{2}\) y \(c_{3}\text{,}\) debemos determinar \(d_{1},d_{2}\) y \(d_{3}\) tales que
\begin{align*} 77d_{1} \amp \equiv 1 \ (\text{mod } 5)\\ 55d_{2} \amp \equiv 1 \ (\text{mod } 7)\\ 35d_{3} \amp \equiv 1\ (\text{mod } 11) \end{align*}
Es muy útil reducir las expresiones en su módulo correspondiente. Es decir, \(77\equiv 2\) (mod \(5\)); por lo que en vez de resolver la congruencia \(77d_{1} \equiv 1 \ (\text{mod } 5)\text{,}\) basta con solucionar \(2d_{1} \equiv 1 \ (\text{mod } 5)\text{.}\) Encontrando los inversos multiplicativos correspondientes, se logra
\begin{align*} d_{1} \amp \equiv 3 \ (\text{mod } 5)\\ d_{2} \amp \equiv 6 \ (\text{mod } 7)\\ d_{3} \amp \equiv 6\ (\text{mod } 11) \end{align*}
De esta manera, la solución final al sistema de congruencias (por el Teorema Chino del Resto) está dada por
\begin{equation*} x\equiv 2\cdot 77\cdot 3+4\cdot 55\cdot 6+5\cdot 35 \cdot 6 \ = 2832 \equiv 137 \ (\text{mod } 385). \end{equation*}
Es decir, \(x\equiv 137 \ (\text{mod } 385).\)

El siguiente interact de Sage permite encontrar la solución de un sistema lineal de congruencia (compuesto por tres ecuaciones).

Sin embargo, que ocurre si queremos determinar la solución del sistema lineal de congruencia:

\begin{align*} 4x \amp \equiv 11 \ (\text{mod } 15)\\ 10x \amp \equiv 8 \ (\text{mod } 12) \end{align*}

Notemos que \((15,12)=3\neq 1\text{,}\) por lo que no es posible utilizar el Teorema Chino del Resto.

Para este tipo de sistemas lineales de congruencia (donde los módulos no son coprimos entre sí), será importante estudiar la descomposición prima de los módulos involucrados. El Ejemplo 3.8.7 muestra como abarcar este tipo de situaciones.

Considere el sistema
\begin{align*} x \amp \equiv 13 \ (\text{mod } 40)\\ x \amp \equiv 5 \ (\text{mod } 44)\\ x \amp \equiv 38\ (\text{mod } 275) \end{align*}
el cual sí posee solución, pero no es directo emplear el Teorema Chino del Resto (ya que los módulos no son coprimos entre sí). En este caso, debemos considerar \(40=5\cdot 2^{3}\text{,}\) \(44=2^{2}\cdot 11\) y \(275=5^{2}\cdot 11\text{.}\) Por lo tanto
\begin{align*} x \amp \equiv 13 \ (\text{mod } 2^{3})\\ x \amp \equiv 13 \ (\text{mod } 5)\\ x \amp \equiv 49 \ (\text{mod } 2^{2})\\ x \amp \equiv 49 \ (\text{mod } 11)\\ x \amp \equiv 38 \ (\text{mod } 5^{2})\\ x \amp \equiv 38\ (\text{mod } 11) \end{align*}
Se deben eliminar ecuaciones. ¿Cúal es el criterio para realizar esto? La expresión que posea la menor potencia de un primo en el módulo, es eliminada. Note que los primos involucrados en el sistema son \(2, 5\) y \(11\text{.}\) Analizando las potencias de tales primos, obtenemos para el 2: \(2< 3\text{.}\) De esta manera, se elimina la expresión \(x \equiv 49 \ (\text{mod } 2^{2})\text{.}\)

Para el 5: \(1< 2\text{.}\) De esta manera, se elimina la expresión \(x \equiv 13 \ (\text{mod } 5)\text{.}\) Para el 11 no podemos aplicar tal criterio. No obstante, se puede eliminar cualquier ecuación (son redudantes, dado que \(49 \equiv 38 \ (\text{mod } 11)\)). Por consiguiente, eliminaremos \(x \equiv 49 \ (\text{mod } 11)\text{.}\) Esto nos permite obtener un sistema reducido, tal que

\begin{align*} x \amp \equiv 5 \ (\text{mod } 8)\\ x \amp \equiv 13 \ (\text{mod } 25)\\ x \amp \equiv 5\ (\text{mod } 11) \end{align*}
La solución del sistema esta expresada en módulo
\begin{equation*} N=8\cdot 25 \cdot 11=2200. \end{equation*}
Debemos encontrar los valores (enteros) de \(c_{1},c_{2}\) y \(c_{3}\) tales que
\begin{align*} c_{1} \amp = \dfrac{2200}{8} = 275\\ c_{2} \amp = \dfrac{2200}{25} = 88\\ c_{3} \amp = \dfrac{2200}{11} = 200 \end{align*}
A partir de \(c_{1},c_{2}\) y \(c_{3}\text{,}\) se debe determinar \(d_{1},d_{2}\) y \(d_{3}\)tales que
\begin{align*} 275d_{1} \amp \equiv 1 \ (\text{mod } 8)\\ 88d_{2} \amp \equiv 1 \ (\text{mod } 25)\\ 200d_{3} \amp \equiv 1\ (\text{mod } 11) \end{align*}
Encontrando (y previamente reduciendo \(275, 88\) y \(200\) en los módulos correspondientes) los inversos multiplicativos de cada ecuación, se logra
\begin{align*} d_{1} \amp \equiv 3 \ (\text{mod } 8)\\ d_{2} \amp \equiv 2 \ (\text{mod } 25)\\ d_{3} \amp \equiv 6\ (\text{mod } 11) \end{align*}
De esta manera, la solución final al sistema de congruencias (por el Teorema Chino del Resto) corresponde a
\begin{equation*} x\equiv 5\cdot 275 \cdot 3+13\cdot 88\cdot 2+5\cdot 200 \cdot 6 \ = 12413 \equiv 1413 \ (\text{mod } 2200). \end{equation*}
Es decir, \(x\equiv 1413 \ (\text{mod } 2200).\)
Encuentre la solución del sistema
\begin{align*} x \amp \equiv 0 \ (\text{mod } 4)\\ x \amp \equiv 4 \ (\text{mod } 6)\\ x \amp \equiv 4\ (\text{mod } 9) \end{align*}

Como se mencionó al comienzo de esta sección, el Teorema Chino del Resto nos permite resolver Ecuaciones Lineales de Congruencia que resultan ser más complejas de lo habitual. Considere el Ejemplo 3.8.9

Encontraremos las soluciones de la ecuación \(119x \equiv 35\) (mod \(1001\)). Esta ecuación posee \(7\) soluciones, ya que \((119,1001)=7\) y \(7|35\text{.}\)

Note que \(1001=7 \cdot 11 \cdot 13\text{.}\) Por lo tanto, la expresión \(119x \equiv 35\) (mod \(1001\)) es equivalente al sistema

\begin{align*} 119x \amp \equiv 35 \ (\text{mod } 7)\\ 119x \amp \equiv 35 \ (\text{mod } 11)\\ 119x \amp \equiv 35 \ (\text{mod } 13) \end{align*}

Simplificando

\begin{align*} 0x \amp \equiv 0 \ (\text{mod } 7)\\ 9x \amp \equiv 2 \ (\text{mod } 11)\\ 2x \amp \equiv 9 \ (\text{mod } 13) \end{align*}
Eliminamos la ecuación \(0x \equiv 0 \ (\text{mod } 7)\) (la cual es redundante). Obtenemos
\begin{align*} 9x \amp \equiv 2 \ (\text{mod } 11)\\ 2x \amp \equiv 9 \ (\text{mod } 13) \end{align*}
Calculando los inversos correspondientes, se consigue
\begin{align*} x \amp \equiv 10 \ (\text{mod } 11)\\ x \amp \equiv 11 \ (\text{mod } 13) \end{align*}
La solución del sistema esta expresada en módulo
\begin{equation*} N=11\cdot 13=143. \end{equation*}
Debemos encontrar los valores (enteros) de \(c_{1}\) y \(c_{2}\) tales que
\begin{align*} c_{1} \amp = \dfrac{143}{11} = 13\\ c_{2} \amp = \dfrac{143}{13} = 11 \end{align*}
Con los valores de \(c_{1}\) y \(c_{2}\text{,}\) debemos determinar \(d_{1}\) y \(d_{2}\) tales que
\begin{align*} 13d_{1} \amp \equiv 1 \ (\text{mod } 11)\\ 11d_{2} \amp \equiv 1 \ (\text{mod } 13) \end{align*}
Encontrando los inversos multiplicativos correspondientes, se logra
\begin{align*} d_{1} \amp \equiv 6 \ (\text{mod } 11)\\ d_{2} \amp \equiv 6 \ (\text{mod } 13) \end{align*}
De esta manera, la solución final al sistema de congruencias (por el Teorema Chino del Resto) es
\begin{equation*} x\equiv 10\cdot 13\cdot 6+11\cdot 11\cdot 6 = 1506 \equiv 76 \ (\text{mod } 143). \end{equation*}
Es decir, \(x\equiv 76 \ (\text{mod } 143)\text{.}\) Por lo tanto
\begin{equation*} x\equiv 76 + 143t, \end{equation*}
con \(t=0,1,2,3,4,5,6\) (siete valores que permiten obtener las soluciones correspondientes). De esta manera, las soluciones de la ecuación \(119x \equiv 35\) (mod \(1001\)) son
\begin{equation*} \left[ 76\right]_{1001}, \left[219 \right]_{1001}, \left[362 \right]_{1001}, \left[ 505\right]_{1001}, \left[ 648\right]_{1001}, \left[ 791\right]_{1001}, \left[ 934\right]_{1001}. \end{equation*}

Al igual que un sistema de ecuaciones, también existen problemas de planteo que involucran sistemas lineales de congruencia. Veamos un ejemplo.

Se reparten cuatro bolsas iguales de caramelos entre tres grupos de niños. En el primer grupo (que tiene cinco niños), se reparten dos bolsas y sobra un caramelo. En el segundo grupo (de seis niños), se reparte una bolsa y sobran dos caramelos. En el tercer grupo (de siete niños), se reparte una bolsa y sobran tres caramelos. Sabiendo que el número total de caramelos no llega a 500, ¿cuántos caramelos contiene cada bolsa?

Sea \(x\text{,}\) la cantidad de caramelos que contiene cada bolsa. El problema puede modelarse mediante el sistema

\begin{align*} 2x \amp \equiv 1 \ (\text{mod } 5)\\ x \amp \equiv 2 \ (\text{mod } 6)\\ x \amp \equiv 3\ (\text{mod } 7) \end{align*}

el cual tiene solución (garantizada por el Teorema Chino del Resto). Además, \(2x \equiv 1 \ (\text{mod } 5)\Leftrightarrow x \equiv 3 \ (\text{mod } 5)\) Por lo tanto, obtenemos un sistema equivalente; tal que

\begin{align*} x \amp \equiv 3 \ (\text{mod } 5)\\ x \amp \equiv 2 \ (\text{mod } 6)\\ x \amp \equiv 3\ (\text{mod } 7) \end{align*}

La solución al sistema estará expresada en módulo

\begin{equation*} N=5\cdot 6 \cdot 7=210. \end{equation*}

Debemos encontrar los valores (enteros) de \(c_{1},c_{2}\) y \(c_{3}\) tales que

\begin{align*} c_{1} \amp = \dfrac{210}{5} = 42\\ c_{2} \amp = \dfrac{210}{6} = 35\\ c_{3} \amp = \dfrac{210}{7} = 30 \end{align*}

Con los valores de \(c_{1},c_{2}\) y \(c_{3}\text{,}\) debemos determinar \(d_{1},d_{2}\) y \(d_{3}\)tales que

\begin{align*} 42d_{1} \amp \equiv 1 \ (\text{mod } 5)\\ 35d_{2} \amp \equiv 1 \ (\text{mod } 6)\\ 30d_{3} \amp \equiv 1\ (\text{mod } 7) \end{align*}

Encontrando los inversos multiplicativos correspondientes, se logra

\begin{align*} d_{1} \amp \equiv 3 \ (\text{mod } 5)\\ d_{2} \amp \equiv 5 \ (\text{mod } 6)\\ d_{3} \amp \equiv 4\ (\text{mod } 7) \end{align*}

De esta manera, la solución final al sistema de congruencias (por el Teorema Chino del Resto) es

\begin{equation*} x\equiv 3\cdot 42\cdot 3+2\cdot 35\cdot 5+3\cdot 30 \cdot 4 \ = 1088 \equiv 38 \ (\text{mod } 210). \end{equation*}

Es decir, \(x\equiv 38 \ (\text{mod } 210).\) Por lo tanto, cada bolsa contiene \(38\) caramelos.

Una banda de 17 piratas se reúne para repartirse un cofre con más de 100 monedas de oro, sobrando 1 moneda después del reparto. En la consiguiente pelea, muere un pirata y vuelve a hacerse el reparto sobrando de nuevo 1 moneda. ¿Cuál es menor número de monedas que puede contener el cofre? Supongamos que la solución anterior es el número real de monedas en el cofre y que la historia continúa: siempre que sobran monedas en el reparto hay pelea y muere un pirata. ¿Cuántos piratas quedarán vivos cuando en el reparto no sobre ninguna moneda?

Finalmente, ¿es posible obtener los últimos dos dígitos de \(5^{12^ {34}}\text{?}\) Evidentemente si, y lo habitual sería utilizar el teorema de Euler - Fermat. Pero lamentablemente esto no es posible, dado que \((5,100)=5\neq 1\text{.}\)

Entonces, ¿cómo resolver esta problemática? Nuevamente el Teorema Chino del Resto nos proporcionará la solución. Considere el Ejemplo 3.8.12.

Encontraremos una manera de calcular los últimos tres dígitos de \(75^{88^ {101}}\text{.}\)

Considere \(x=75^{88^ {101}}\text{.}\) Como queremos obtener los últimos tres dígitos de \(x\text{,}\) debemos trabajar en módulo 1000 (¿por qué?). No podemos utilizar el Teorema de Euler - Fermat; ya que \((75,1000)=5\neq 1\text{,}\) pero sí el Teorema Chino del Resto. Ya que \(1000=2^{3}\cdot 5^{3}\text{,}\) entonces

\begin{align*} x \amp \equiv 75^{88^ {101}} \ (\text{mod } 8)\\ x \amp \equiv 75^{88^ {101}} \ (\text{mod } 125) \end{align*}
Por otro lado, \(75 \equiv 3 \ (\text{mod } 8)\text{.}\) Esto implica, \(75^{88^ {101}} \equiv 3^{88^ {101}} \ (\text{mod } 8)\text{.}\) Dado que \((3,8)=1\text{,}\) podemos utilizar el Corolario 3.6.11. Note que \(88^ {101}\equiv 0 \ (\text{mod } 4)\text{,}\) pues \(4|88\text{.}\) Por Corolario 3.6.11
\begin{equation*} 3^{88^ {101}} \equiv 3^{0}=1 \ (\text{mod } 8). \end{equation*}
Así, \(x\equiv 1 \ (\text{mod } 8)\text{.}\) Por otro lado
\begin{equation*} 75^{88^ {101}} = 75^{88\cdot 88^ {100}} = (75^{2})^{44\cdot 88^{100}}=5625^{44\cdot 88^{100}} \equiv 0 \ (\text{mod } 125). \end{equation*}
Por lo tanto, \(x\equiv 0 \ (\text{mod } 125)\text{.}\) Esto nos permite construir el sistema
\begin{align*} x \amp \equiv1 \ (\text{mod } 8)\\ x \amp \equiv 0\ (\text{mod } 125) \end{align*}
cuya solución está dada por \(x\equiv 625 \ (\text{mod } 1000)\text{.}\) Por lo tanto los últimos tres dígitos de \(75^{88^ {101}}\) son \(6, 2\) y \(5\text{.}\)
Obtenga los últimos tres dígitos de \(5^{12^ {34}}.\)