$13^{11^{7^{5^{3^2}}}}\bmod 100$ - verificación de la respuesta

Question

$13^{11^{7^{5^{3^2}}}}\bmod100=37$, de acuerdo a WolframAlpha. Mis cálculos siempre el mismo resultado, sin embargo, tras el examen, me di cuenta de que no tiene sentido, aunque el resultado es correcto. Yo lo que hice fue, a partir de la parte superior, he calculado que cada exponente $\bmod 100$. $3^2\equiv 9, 5^9\equiv25, 7^{25}\equiv 7, 11^7\equiv 71, 13^{71}\equiv37\bmod100$. Pero luego me di cuenta, yo debería haber estado tomando todo lo $\bmod\phi(100)=40$. Pero, ¿por qué esta obra? Es cuestión de suerte? También, hay una manera más rápida de que esto?

Answer 1

$\lambda(100)=20$

$$13^{11^{7^{5^{3^2}}}}\equiv13^{11^{7^{5^{3^2}}}\pmod{20}}\bmod100$$

Ahora $11^{2m+1}=11(1+10)^{2m}\equiv11(1)\pmod{20}$

Ahora $13^{11}=13(170-1)^5\equiv13(-1+5\cdot170)\pmod{100}\equiv50-13$

Aquí $2m+1={7^{5^{3^2}}}$

Answer 2

Si usted fuera a hacer esto en su cabeza, la primera cosa a tener en cuenta es que no es la función de euler, sino más bien el período que importa. Por 100, esto es 20. Que es $100 \mid x^{20}-1$.

La manera de averiguar esto, es tomar el mínimo común múltiplo de euler-la función de cada uno de los prime-poder, por lo $\mbox{lcm}(\phi(4), \phi(25)$. La razón para esto puede ser visto en el período de 91 en decimal. A pesar de $\phi(91)=72$, los ciclos de 7 (ie $\phi(7)=6$ y 13 ($\phi(13)=12$) correr lado a lado.

Útil saber es que el 7 tiene 5 como sevenite, que es, $5^2 \mid 7^{5-1}-1$.

Esto significa que estamos buscando primero para ${11^x} \mbox{ for } x\pmod{20}$, y, a continuación,${7^x}\mbox{ for } x\pmod{4}$.

Por lo ${5^x=1}\pmod{4}$ siempre

A continuación, ${7^x=7}\pmod{20}$ cuando x=1, mod 4

A continuación,${11^7=71}\pmod{100}$, es fácil encontrar en el triángulo de pascal.

La adición de 13 a la mezcla no presenta ningún problema. 71 reduce a 11, modulo 20.

Luego buscamos $13^{11}$. Tenga en cuenta que $13^2 = 1,7,-1$ base 10. Su décima potencia es entonces $13^{10}=,,,5\times 7,-1$ o 49. Encontramos entonces que el 13*49=13*50-13, o 50-13, o 37.

Porque 100 es múltiplo de su período de duración, se puede seguir utilizando la torre de los números primos, sin más ajustes.

Todo se hace mediante el cálculo mental.

Answer 3

Siempre trabaje desde la parte inferior hasta la parte superior de la torre es bastante probable a ser irrelevante.

Así, desde el fondo, estamos interesados en el orden de $13 \bmod 100$. El Carmichael función de $\lambda$ es útil aquí; sabemos que el orden de $13$ divide $\lambda(100)=20$. Podríamos comprobar para ver si $13$ obviamente tiene cualquier orden inferior, pero también podemos dejar que, por ahora.

Así que estamos interesados en el orden de $11 \bmod 20$. Esto es evidente de inmediato a ser $2$, ya que el $11^2=121 \equiv 1 \bmod 20$. De hecho, este es un ejemplo de un patrón común, $(2n\pm 1)^2\equiv 1 \bmod 4n$.

Así que ahora sólo tenemos que saber si el exponente de la $11$ es par o impar. Y es que algunos de gran potencia de $7$, por lo que es extraño, y esto nos da:

$$13^{11^{7^{5^{3^2}}}} \equiv 13^{11}\bmod 100$$

Podemos calcular esto de varias maneras, pero la exponenciación al cuadrado no es demasiado caro, especialmente porque puedo usar el patrón de plazas $\bmod 100$ que se repite en $50$.

$\bmod 100: \\ 13^2\equiv 69 \\ 13^4\equiv 69^2 \equiv 19^2 \equiv 61 \\ 13^5\equiv 61\cdot 13 \equiv 93 \equiv -7 \\ 13^{10} \equiv (-7)^2\equiv 49 \\ 13^{11} \equiv 49 \cdot 13 \equiv 37$