Resolver a^(b^c) usando el pequeño teorema de Fermats

Question

¿Cómo puedo encontrar la solución de la siguiente ecuación?

$a^{(b^c)} \equiv x \;(\bmod\; n)$

(suponer $n$ no divide $a$ a los efectos de utilizar el pequeño teorema de Fermats)

Supongamos que a y b pueden ser valores algo pequeños alrededor de 5 a 100 y c puede tomar valores de 1.000 a 10.000. ¿Cuál es el algoritmo general para resolver $x$ ¿usando papel y bolígrafo?

Esta pregunta me parece bastante confusa por los 3 exponentes. Puedo resolver problemas regulares del tipo $a^{b} \equiv x \;(\bmod\; n)$ pero debo estar perdiéndome algo con esto.

Ejemplos de problemas:

$2^{(6^{2015})} \equiv x \;(\bmod\; 19)$ - encontrar $x$

$2^{(6^{2015})} \equiv y \;(\bmod\; 23)$ - encontrar $y$ - realmente necesito ayuda con esto

Answer 1

$23$ es primo por lo que $2^{22} \equiv 1 \mod 23$

Así que $2^{6^{2015}} \equiv 2^k \mod 23$ donde $6^{2015} \equiv k \mod 22$ por lo que debemos resolver $6^{2015}\equiv k \mod 22$ .

Utiliza el teorema chino del resto. $22 = 2*11$

$6^{2015} \equiv 6^5 \mod 11$ así que $6^5 = 36*36*6\equiv 3*3*6 \equiv 54 \equiv -1 \mod 11$ y $6^{2015} \equiv 0 \mod 2$ .

Así que $6^{2015} \equiv 10 \mod 22$ .

Así que $2^{6^{2015}} \equiv 2^{10} \equiv 1024\equiv 12 \mod 23$ .

\====

No estoy familiarizado con el teorema del Resto Chino, ¿significa que puedo simplemente dividirlo en dos preguntas separadas de los dos factores 2 y 11, simplemente sumo los resultados entonces? Y también.. ¿cómo consigo la primera parte en la que se pasa a mod 22 para resolver k?

Bien, detalles.

Por FLT $2^{22} \equiv 1 \mod 23$

Así que si $6^{2015} = 22m + r$ entonces $2^{5^{2015}}\equiv 2^{22m + r} \equiv (2^{22})^m*2^k \equiv 1*2^k \equiv 2^r \mod 23$ .

Así que debemos resolver $6^{2015} = 22m + r$ o en otras palabras debemos resolver $6^{2015} \equiv r \mod 22$ .

Pregunta 1: ¿Qué es $6^{2015} \equiv r \mod 22$ .

Ahora no podemos usar FLT porque $6$ y $22$ no son relativamente primos.

Pero podemos utilizar el Teorema del resto chino que dice.

Si $n,m$ son relativamente primos y si $x \equiv a \mod n$ y $x \equiv b \mod m$ entonces hay una solución única para $x \mod nm$ .

Así que $22 = 2*11$ y $\gcd (2,11) = 1$ .

Así que si $x \equiv 6^{2015}\equiv 0 \mod 2$

y $x \equiv 6^{2015} \equiv (6^{10})^{201}*6^5 \equiv 6^5\equiv 10 \mod 11$

Entonces habrá una solución única $6^{2015}\equiv x \mod 22$ .

Ahora $0 \equiv 10 \mod 2$ y $10 \equiv 10 \mod 11$ . Y $10 \equiv 10 \mod 22$ . así que $x \equiv 10 \mod 22$ es a solución a $x\equiv 0 \mod 10$ y $x\equiv 10 \mod 11$ . Y por el teorema del resto chino es un único solución.

Así que $6^{2015}\equiv 10 \mod 22$ .

Así que $6^{2015} = 22m + 10$ .

Así que $2^{6^{2015}} = 2^{22m + 10} \equiv (2^{22})^{m}*2^{10} \equiv 2^{10}\equiv 1024\equiv 12 \mod 23$ .

\=====

De acuerdo, sin CRT. Todavía tenemos que encontrar $6^{2015} \mod 22$ .

$6^2 = 36 \equiv 14\equiv -8\mod 22$

$6^3 \equiv -8*6 \equiv -48 = -4 \mod 22$ .

$6^4 \equiv -24 \equiv -2 \mod 22$

$6^5 \equiv -12 \equiv 10 \mod 22$

$6^6 \equiv 60 \equiv -6 \mod 22$

Así que $6^{2015} \equiv 6^{6*335+5}\equiv (-6)^{335}*6^{5}$

$\equiv (-6)^{6* 55+ 5}*10$

$\equiv (-6)^{55}*(-10)*10$

$ \equiv (-6)^{6*9 + 1}*(-100)$

$\equiv (-6)^9*(600)$

$\equiv (-6)^{6+3}* 6$

$\equiv (-6)*(-6)^3*6$

$\equiv 6^5 \equiv 10 \mod 22$ .