How to compute $\,3^{3^{3^{\:\!\phantom{}^{.^{.^.}}}}}\!\!\!\!\bmod 46,$ for power tower height $2020$?

What is the remainder of $\,3^{3^{3^{\:\!\phantom{}^{.^{.^.}}}}}\!\!\!$ divided by $46$? The level of powers is $2020$.

First there is no parenthesis so it means 3 power of 3 which is also power 3 and so on 2020 times

Second I think that we can use Fermat's Little Theorem but I don't know how, and maybe there is a better way.

Solution 1:

We can easily apply Euler's totient theorem here several times

$\varphi(46)=\varphi(2)\varphi(23)=22$

$\varphi(22)=\varphi(2)\varphi(11)=10$

$\varphi(10)=\varphi(2)\varphi(5)=4$

$\varphi(4)=2$

$\varphi(2)=1$

since they are all coprime to $3$. This gives the result:

\begin{align}R&=3\widehat~(3\widehat~(3\widehat~(3\widehat~(3\widehat~n))))\bmod46\\&=3\widehat~(3\widehat~(3\widehat~(3\widehat~(3\widehat~(n\bmod1)\bmod2)\bmod4)\bmod10)\bmod22)\bmod46\\&=3\widehat~(3\widehat~(3\widehat~(3\widehat~(3\widehat~1\bmod2)\bmod4)\bmod10)\bmod22)\bmod46\\&=3\widehat~(3\widehat~(3\widehat~(3\widehat~1\bmod4)\bmod10)\bmod22)\bmod46\\&=3\widehat~(3\widehat~(3\widehat~3\bmod10)\bmod22)\bmod46\\&=3\widehat~(3\widehat~7\bmod22)\bmod46\\&=3\widehat~9\bmod46\\&=41\end{align}

for any value of $n$.