$a_1=3;\ a_{n+1}=3^{a_n}$; find $a_{2004}\bmod100$ A detailed solution will be helpful. Given that $a_1=3$ and $a_{n+1}=3^{a_n}$, find the remainder when $a_{2004}$ is divided by 100.
 A: Note that $a_{2004} = 3^{3^{.^{.^{.^{3}}}}}$ where the length of the exponent tower is $2003$. Anyway all we need to apply is Euler's Totient Formula. As $\phi(100) = 40$, so now we consider: $3^{3^{.^{.^{.^{3}}}}} \bmod {40}$ where the tower length is $2002$. Continue in this manner and we will consider $\phi(40) = 16$, later on $\phi(16) = 8$.
Now we do a simple back tracking. As we know that $3$ to an odd exponent is equal to $3$ modulo $8$ we have: $3^{3^{.^{.^{.^{3}}}}} \equiv 3 \pmod 8$. Then $3^{3^{.^{.^{.^{3}}}}} \equiv 3^3 \equiv 11 \pmod{16}$. Then $3^{3^{.^{.^{.^{3}}}}} \equiv 3^{11} \equiv 27 \pmod{40}$. And at the end:
$$a_{2004} = 3^{3^{.^{.^{.^{3}}}}} \equiv 3^{27} \equiv 87 \pmod{100}$$
NOTE: For the exponents I used the same symbol, although the length of the tower varies, but I guess that should be understandable.
A: $$a_1=3$$
$$a_2=3^3=27$$
$$a_3=3^{27}$$
Consider $a_4=3^{3^{27}}$. By Euler's theorem this is congruent to $3^{3^{27}\bmod40}$ modulo 100. Since $3^4\equiv1\bmod40$, $3^{27}\equiv3^3\equiv27\bmod40$. Thus we have the relation
$$3^{3^{27}}\equiv3^{27}\bmod100$$
In other words, exponentiating by 3 does not change the residue. Hence $a_n\equiv87\bmod100$ for $n\ge3$, and the answer is 87.
A: By the CRT, in order to find $a_{2004}\pmod{100}$ it is enough to find $a_{2004}\pmod{8}$ and $a_{2004}\pmod{25}$. Now $a_n=3^{a_{n-1}}\pmod{8}$ just depends on $a_{n-1}\pmod{4}$, and $a_{n-1}=3^{a_{n-2}}\pmod{4}$ just depends on $a_{n-2}$ being even or odd. Since $a_{2002}$ is clearly odd, $a_{2003}\equiv 3\pmod{4}$ and $\color{green}{a_{2004}\equiv 3\pmod{8}}$. $a_n=3^{a_{n-1}}\pmod{25}$ just depends on $a_{n-1}\pmod{20}$. We already know that $a_{2003}\equiv 3\pmod{4}$, hence it is enough to find $a_{2003}=3^{a_{2002}}\pmod{5}$, or $a_{2002}\pmod{4}$. Since $a_{2002}\equiv 3\pmod{4}$, $a_{2003}\equiv 2\pmod{5}$, hence $a_{2003}\equiv 7\pmod{20}$ and $\color{green}{a_{2004}\equiv 12\pmod{25}}$. Putting together the green identities,
$$ \color{green}{\large a_{2004}\equiv 87\pmod{100}.}$$
You may notice that the above argument has little to do with the arithmetic properties of $2004$, and in fact you may apply the same argument to show that $a_n\equiv 87\pmod{100}$ for any $n\geq 3$.
This is due to the fact that by iterating the totient function, we always reach $1$ pretty soon.
For instance:
$$\varphi(\varphi(\varphi(\varphi(\varphi(\varphi(100))))))=1.$$
