<s>[INST] Find the remainder of 3^3^3...^3 divided by 46 Find the remainder of $3^{{{{{3^3}^3}^3}^3}^\cdots} \text{(2020 copies of 3)}$ by 46
Note that $a^{b^c}$ means $a^{(b^c)}$ not $(a^b)^c$
If there was 2 copies of 3:
$3^3\equiv27 (mod 46)$.
If there was 3 copies of 3:
$3^{3^3}\equiv3^{27}\equiv(3^9)^3\equiv(19683)^3\equiv(41)^3\equiv68921\equiv13(mod46)$
However I can't repeat this process 2020 times. How to solve this?
 [/INST] Since $3$ is odd, for all odd $k$ we have $3^k$ is odd, and $3^k=3\pmod 4$.
Now consider
$$
x_0 = 3^{3^{3^{3^{k}}}}, x_1 = 3^{3^{3^{k}}}, x_2 = 3^{3^{k}}, x_3 = 3^{k}
$$
where $k = 3^{3^{⋰^{3}}}$ is the remaining part of the exponent.
We have

*

*$x_0$ is computed modulo $46$, and $x_0 = 3^{x_1} \pmod {46}$

*$x_1$ is computed modulo $\varphi(46)=22$, and $x_1 = 3^{x_2} \pmod {22}$

*$x_2$ is computed modulo $\varphi(\varphi(46))=10$, and $x_2 = 3^{x_3} \pmod {10}$

*$x_3$ is computed modulo $\varphi(\varphi(\varphi(46))=4$
But $k$ is odd, so $x_3 = 3^k = 3 \pmod 4$.
Then $x_2 = 3^3 = 7 \pmod {10}$.
Then $x_1 = 3^7 = 9 \pmod {22}$.
Then $x_0 = 3^9 = 41 \pmod {46}$.
So as long as the tower has more than 4 elements, the result will be $41 \pmod {46}$.
</s>