$a_1=3;\ a_{n+1}=3^{a_n}$; encontrar $a_{2004}\bmod100$

Question

Una solución detallada será útil. Dado que el$a_1=3$$a_{n+1}=3^{a_n}$, hallar el resto al $a_{2004}$ se divide por 100.

Answer 1

Tenga en cuenta que $a_{2004} = 3^{3^{.^{.^{.^{3}}}}}$ cuando la longitud de la exponente de la torre es $2003$. De todos modos todo lo que tenemos que aplicar es el de Euler Totient Fórmula. Como $\phi(100) = 40$, así que ahora tenemos que considerar: $3^{3^{.^{.^{.^{3}}}}} \bmod {40}$ donde se encuentra la torre de la longitud de es $2002$. Continuar de esta manera y vamos a considerar $\phi(40) = 16$, más adelante en $\phi(16) = 8$.

Ahora hacemos un simple seguimiento. Como sabemos que $3$ a un exponente impar es igual a $3$ modulo $8$ tenemos: $3^{3^{.^{.^{.^{3}}}}} \equiv 3 \pmod 8$. A continuación,$3^{3^{.^{.^{.^{3}}}}} \equiv 3^3 \equiv 11 \pmod{16}$. A continuación,$3^{3^{.^{.^{.^{3}}}}} \equiv 3^{11} \equiv 27 \pmod{40}$. Y al final:

$$a_{2004} = 3^{3^{.^{.^{.^{3}}}}} \equiv 3^{27} \equiv 87 \pmod{100}$$

NOTA: Para los exponentes he utilizado el mismo símbolo, aunque la duración de la torre varía, pero supongo que debe ser comprensible.

Answer 2

$$a_1=3$$ $$a_2=3^3=27$$ $$a_3=3^{27}$$ Considere la posibilidad de $a_4=3^{3^{27}}$. Por el teorema de Euler esto es congruente a $3^{3^{27}\bmod40}$ modulo de 100. Desde $3^4\equiv1\bmod40$, $3^{27}\equiv3^3\equiv27\bmod40$. Así pues, tenemos la relación $$3^{3^{27}}\equiv3^{27}\bmod100$$ En otras palabras, exponentiating por 3 no cambia el residuo. Por lo tanto $a_n\equiv87\bmod100$$n\ge3$, y la respuesta es de 87.

Answer 3

Por la CRT, con el fin de encontrar $a_{2004}\pmod{100}$ es suficiente para encontrar $a_{2004}\pmod{8}$$a_{2004}\pmod{25}$. Ahora $a_n=3^{a_{n-1}}\pmod{8}$ sólo depende de $a_{n-1}\pmod{4}$, e $a_{n-1}=3^{a_{n-2}}\pmod{4}$ sólo depende de $a_{n-2}$ ser pares o impares. Desde $a_{2002}$ es claramente impar, $a_{2003}\equiv 3\pmod{4}$ y $\color{green}{a_{2004}\equiv 3\pmod{8}}$. $a_n=3^{a_{n-1}}\pmod{25}$ sólo depende de $a_{n-1}\pmod{20}$. Ya sabemos que $a_{2003}\equiv 3\pmod{4}$, por lo tanto es suficiente para encontrar $a_{2003}=3^{a_{2002}}\pmod{5}$ o $a_{2002}\pmod{4}$. Desde $a_{2002}\equiv 3\pmod{4}$, $a_{2003}\equiv 2\pmod{5}$, por lo tanto $a_{2003}\equiv 7\pmod{20}$$\color{green}{a_{2004}\equiv 12\pmod{25}}$. Armar el verde de las identidades, $$ \color{green}{\large a_{2004}\equiv 87\pmod{100}.}$$ Usted puede notar que el argumento anterior tiene poco que ver con las propiedades aritméticas de $2004$, y de hecho se puede aplicar el mismo argumento para demostrar que $a_n\equiv 87\pmod{100}$ cualquier $n\geq 3$.
Esto es debido al hecho de que por iteración en la totient función, que siempre llegan a $1$ muy pronto.
Por ejemplo: $$\varphi(\varphi(\varphi(\varphi(\varphi(\varphi(100))))))=1.$$