Encuentra los 3 últimos dígitos de la potencia de la potencia donde la base es enorme

Question

Dado $a=135797531$ , encuentre los 3 últimos dígitos de $a^{a^{320}}$ .

Ahora, sé que tengo que resolver: $a^{a^{320}}(\mod 1000)$ .

Lo que sé: $a\in{U_n}$ (Grupo de Euler - Grupo multiplicativo de enteros módulo n) por lo que se aplica el teorema de Euler y $a^{\phi(1000)}\equiv1(\mod 1000)$ donde $\phi(1000)=400$ .

También vi aquí que el exponente es congruente con el exponente módulo $\phi(1000)$ pero no entiendo por qué y en qué condiciones..

No sé cómo continuar desde aquí ¡ayuda!

Answer 1

Teorema : Si $b$ y $c$ son números naturales no negativos, $m$ y $a$ son coprimas, $b = c\enspace\text{mod}\,\varphi(m)$ entonces $a^b = a^c\enspace\text{mod}\,m$ .

Prueba : Sin pérdida de generalidad, supongamos que $b>c$ . Entonces $b=c+k\cdot\varphi(m)$ donde $k$ es un número natural. $$a^b = a^{c+k\cdot\varphi(m)} = a^c\cdot (a^{\varphi(m)})^k = a^c \enspace\text{mod}\,m$$

Donde utilizamos el teorema de Euler para $a^{\varphi(m)} = 1\enspace\text{mod}\,m$ y el hecho de que $$a'=a''\enspace\text{mod}\,m\,\land\,b'=b''\enspace\text{mod}\,m\implies a'b'=a''b''\enspace\text{mod}\,m$$

Fin de la prueba .

Supongamos que queremos calcular $a^{a^{320}}$ modulo $1000$ . Primero podemos calcular $a^{320}$ modulo $\varphi(1000)=400$ desde $a$ y $1000$ son coprimas, utilizando el teorema anterior.

Para calcular $a^{320}$ modulo $400$ podemos calcular $320$ modulo $\varphi(400)=160$ Porque, de nuevo, $400$ y $a$ son coprimas.

$$320 = 0\enspace\text{mod}\,160 \implies a^{320} = 1\enspace\text{mod}\,400 \implies a^{a^{320}}=a\enspace\text{mod}\,1000$$ Y porque $a=531\enspace\text{mod}\,1000$ entonces $$a^{a^{320}}=531\enspace\text{mod}\,1000$$