Cómo calcular $7^{7^{7^{100}}} \bmod 100$ ?

Question

Cómo calcular $7^{7^{7^{100}}} \bmod 100$ ? Es $$7^{7^{7^{100}}} \equiv7^{7^{\left(7^{100} \bmod 100\right)}} \bmod 100?$$ Muchas gracias.

Answer 1

En primer lugar, hay que tener en cuenta que $$7^4 \equiv 1 \pmod{100}$$ Por lo tanto, obtenemos que $$7^n \equiv \begin{cases}1 \pmod{100} & n \equiv 0 \pmod4\\ 7 \pmod{100} & n \equiv 1 \pmod4\\ 49 \pmod{100} & n \equiv 2 \pmod4\\ 43 \pmod{100} & n \equiv 3 \pmod4 \end{cases}$$ Por lo tanto, todo lo que tenemos que averiguar es $7^{7^{100}} \pmod 4$ . Desde $7 \equiv (-1) \pmod4$ tenemos que $$7^{7^{100}} \equiv -1^{\text{odd}} \pmod 4 \equiv -1 \pmod 4 \equiv 3 \pmod 4$$ Por lo tanto, $$7^{7^{7^{100}}} \equiv 43 \pmod{100}$$

Answer 2

$7^4\equiv1\pmod{100}$

Dejemos que $$y=7^{7^{7^{100}}}$$

Así que, $7y=7^{(7^{7^{100}}+1)}\equiv1\pmod{100}$ como $(7^{7^{100}}+1)$ es divisible por $(7+1)=8$

Utilicemos la propiedad de las sucesivas convergentes de una fracción continua.

Ahora, $\frac{100}7=14+\frac27=14+\frac1{\frac72}=14+\frac1{3+\frac12}$

Por lo tanto, la convergencia anterior de $\frac{100}7$ es $14+\frac13=\frac{43}3$

Así que, $100\cdot3-7\cdot43=-1\implies y\equiv43\pmod {100}$

Answer 3

Como gcd(7, 100) = 1 puedes utilizar el teorema del totiente de Euler.

$7^{\phi(100)} \equiv 7^{40} \equiv 1 \bmod 100$

donde $ \phi(n) $ es la función totiente de Euler.

También hay que tener en cuenta que $7^{\phi(40)} \equiv 7^{16}\equiv 1 \bmod 40 $

así que

$7^{7^{7^{100}}} \equiv 7^{(7^{7^{100}} \bmod 40)} \equiv 7^{(7^{(7^{100} \bmod 16} \bmod 40)} \bmod 100$

$7^{100} \equiv 1 \bmod 16 $

$7^{7^{7^{100}}} \equiv 7^{(7^{(7^{100} \bmod 16} \bmod 40)} \equiv 7^{(7^{1} \bmod 40)} \equiv 7^{7} \equiv 43 \bmod 100 $

En general, si quiere saber $a^{b^{c^{d}}} \bmod m$ es igual a $a^{b^{(c^{d \mod m_3} \mod m_2)} \mod m_1} \bmod m$

donde $ m_1 = \phi(m)$ , $ m_2 = \phi(m_1)$ , $ m_3 = \phi(m_2)$

siempre que

$\gcd(a, m) = 1,$

$\gcd(b, m_1) = 1$ y

$\gcd(c, m_2)=1 $ .

Si no es así, hay un truco que puedes utilizar $a^{b \mod \phi(m) + \phi(m)} \bmod m $ en lugar de $a^{b \mod \phi(m)} \bmod m.$

Estaba tratando de conseguir una discusión en cálculo de exponentes anidados módulo n bajo qué circunstancias exactamente funciona este truco, pero mis esfuerzos fueron infructuosos. Si alguien sabe algo al respecto, por favor considere visitarlo y ayudar.