<s>[INST] $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.
 [/INST] 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.$$
</s>