Calcula: $177^{20^{100500}}\pmod{60}$

Question

Estoy dando mis primeros pasos en la aritmética modular y ya estoy atascado.

Calcula:

$$177^{20^{100500}}\pmod{60}$$

No sé cómo abordar este tema. Hasta ahora he estado aplicando el Teorema de Euler y el Pequeño Teorema de Fermat para calcular expresiones más sencillas, pero aquí observamos que $\mathrm{gdc}(177,60) = 3 \neq 1$ por lo que, a mi entender, no puedo aplicar ninguno de los dos teoremas. En su lugar, he probado lo siguiente:

\begin {align} 177^{20^{100500}} \pmod {60} & \equiv (3 \cdot 59)^{20^{100500}} \bmod 60 \\ & \equiv (3 \bmod 60)^{20^{100500}} \cdot (59 \bmod60 )^{20^{100500}} \\ & \equiv (3 \bmod 60)^{20^{100500}} \cdot (-1)^{20^{100500}} \end {align}

Desde $20^{n}$ es incluso $\forall n \in \mathbb{N}$ entonces $(-1)^{20^{100500}} = 1$ . Por lo tanto,

$$177^{20^{100500}} \pmod{60}\equiv 3\ (\mathrm{mod}\ 60)^{20^{100500}}$$

Pero no tengo ni idea de qué hacer aquí.

Gracias por su ayuda.

Answer 1

Has tenido un buen comienzo.

Ya conoces el teroema de Euler, y el totiente de Euler, así que puedo añadir otra herramienta a la caja con el Función de Carmichael $\lambda$ que le dará la mayor longitud de ciclo exponencial (y todavía un valor que todos los ciclos más cortos dividirán). Esto combina los valores de las potencias primos a través del mínimo común múltiplo en lugar de la simple multiplicación como para el totiente de Euler.

Aquí $\lambda(60) ={\rm lcm}(\lambda(2^2),\lambda(3),\lambda(5)) ={\rm lcm}(2,2,4) =4$ . Así que para cualquier número impar $a$ ya que no hay potencias primarias Impares superiores en $60$ Tendrá $a^{k+4}\equiv a^k \bmod 60$ para $k\ge 1$ . (Para los números pares puede necesitar $k\ge 2$ ya que $2^2 \mid 60$ ). Así que $20^{100500}$ es sólo un enorme múltiplo de $4$ y podemos expulsar a todos aquellos $4$ s todo el camino hasta $3^4$ . Así que el resultado final es

$$177^{20^{100500}} \equiv \underset {(\text{your result})}{3^{20^{100500}}}\equiv \underset {(\lambda(60)=4)}{3^4}\equiv 81\equiv 21 \bmod 60$$

Answer 2

La forma más sencilla de manejar estas potencias extremas es calcular la potencia módulo $3$ , $4$ y $5$ y aplicar el teorema del resto chino. Estos cálculos de módulos no son muy difíciles:

Módulo $3$ es trivial; $177$ es divisible por $3$ , por lo que el residuo es $0$ .

Módulo $4$ también es trivial; $177$ tiene un residuo $1$ modulo $4$ , por lo que el poder tiene residuos $1$ modulo $4$ también.

Para Modulo $5$ se puede reducir el exponente módulo $4$ , lo que da $0$ por lo que el residuo módulo $5$ es $2^0=1$ .

Entonces, el poder es congruente $0$ modulo $3$ , $1$ modulo $4$ y $1$ modulo $5$ . Eso da $21$ modulo $60$

Answer 3

$3^5=3\pmod{60}$ así que toma el exponente modulo $4$ y luego comprueba si necesitas multiplicar por $-1$ .

Answer 4

La respuesta es $21$ . La prueba es la siguiente:

Lo primero que hay que observar es que la secuencia $$a_n=177^n\mod{60}$$ es periódica con periodo $4$ . Empieza así: ${57, 9, 33, 21, 57, 9, 33, 21,...}$ . Esto se puede demostrar por inducción. Por lo tanto, si $n$ es un múltiplo de $4$ , $a_n=21$ . El exponente $20^m$ es un múltiplo de $4$ para todos los enteros positivos $m$ lo que completa la prueba.