Find last two digits of $4^{4^{4^{...}}}$ - overall 2013 of 4 (including first)

Question

My thoughts: this can be rewritten as $256^{256^{256^{...}}}$

As number of 4 is odd, this number eventually will be $(256^{256^{256^{...}}})^4$

Also, among all reminders which can leave $56^{k} \mod3$ only 16 fits, as $4^k \mod 3 \equiv 1$.

So it is last to digits of $16^4$ = 36

However, I don't feel confidence here.

Answer 1

$4^{4^{4^{\cdots}}} \bmod 100$ can be found by examining the successive steps up the tower.

$4^k \bmod 100$ will have a cycle length that divides $10$, since the Carmichael function $\lambda(100)=20$ guarantees that the cycle length of $2$ will divide $20$.

Considering $k= 4^m \bmod 10$, then, this will have a cycle length dividing $\lambda(10)=4$ (actually, $2$). And since we already know that $4 \mid m$, we can calculate that immediately as $k \equiv 6 \bmod 10$.

Then $4^{4^{4^{\cdots}}} \equiv 4^6 \equiv 56\cdot 16 \equiv \fbox{96} \bmod 100$

Answer 2

$4^k\equiv 0\pmod{4}$ for any $k>0$.

So you really want to figure out $4^k\pmod{25}$.

Now, $4^{10}\equiv 1 \pmod{25}$.

Now if $k=4^l$ for some even $l>0$, the $k\equiv 0\pmod{2}$ and $k\equiv (-1)^l=1\pmod{5}$, so $k\equiv 6\pmod{10}$ and thus $4^{k}\equiv 4^{6}\equiv 21\pmod{25}$.

Then $4^{4^{l}}\equiv 96\pmod{100}$ for all even $l>0$.