$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?
Respuestas
¿Demasiados anuncios?
Simon D
Puntos
1414
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.
Joffan
Puntos
7855
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 $
