How to find $3^{3^{3^{\dots}}}\pmod{100}$?

Question

I can show that $3^{3^{3^n}}\equiv7\pmod{10}$ since

$3^1\equiv3\pmod{10}$

$3^2\equiv9\pmod{10}$

$3^3\equiv7\pmod{10}$

$3^4\equiv1\pmod{10}$

Thus, it reduces to $3^{(3^{3^n}\mod4)}$. I can then notice that

$3^1\equiv3\pmod4$

$3^2\equiv1\pmod4$

Reducing it down to $3^{(3^{(3^n\mod2)}\mod4)}=3^{(3^1\mod4)}=3^3\equiv7\pmod{10}$

However, this is tedious and not capable of solving the following problem:

$$3^{3^{3^{\dots}}}\pmod{100}$$

where the power tower keeps going up until the value becomes fixed for all further power towers. How would I take this problem?

To clarify a bit, we take the exponents at the top and work our way down. For example,

$$3^{3^3}=3^{27}\ne(3^3)^3$$

For clearer notation, $3^{3^{3^{\dots}}}=3\uparrow(3\uparrow(3\uparrow(\dots(3\uparrow n)\dots)))$, and we take as many $\uparrow$'s required such that for all $n,k\in\mathbb N$ we have

$$3\uparrow(3\uparrow(3\uparrow(\dots(3\uparrow n)\dots)))\equiv3\uparrow(3\uparrow(3\uparrow(\dots(3\uparrow k)\dots)))\pmod{100}$$

In Knuth's up arrow notation.

Answer 1

We know that $$3^2 \equiv 1 \pmod{4} \\ 3^{20} \equiv 1 \pmod{25}$$ with the last following from Euler Theorem. Therefore $$3^{20} \equiv 1 \pmod{100}$$

The problem then reduces to finding the powers of $3 \pmod{20}$.

Again $$3^2 \equiv 1 \pmod{4} \\ 3^4 \equiv 1 \pmod{5} \\$$

Therefore $3^4 \equiv 1 \pmod{20}$.

We thus have $$3^{3^{3 ^{...}}} \equiv 3^{3^{3 ^{...}} \pmod{20}} \equiv 3^{3^{3 ^{...} \pmod{4}}} \pmod{100} \equiv 3^{3^{3 }} \pmod{100}\\ \equiv 3^{27}\equiv 3^{7} \pmod{100}$$ which is easy to calculate.

Answer 2

As $3\equiv-1\pmod4,3^{2n+1}\equiv-1\equiv3$ for any integer $n\ge0$

So, $3^{3^{3^{\cdots}}}$ can be written as $\displaystyle3^{4k+3}$ or $\displaystyle3^{3^{(4b+3)}}$

Now,$\displaystyle3^{4k+3}=27(10-1)^{2k}=27(1-10)^{2k}$

and $\displaystyle(1-10)^{2k}\equiv1-\binom{2k}110\pmod{10^2}\equiv1-20k$

So, it is sufficient to find $4k+3=3^{(4b+3)}\pmod5$

$\displaystyle4k+3=3^{(4b+3)}=3^3(3^4)^b\equiv2\cdot1^b\pmod5\equiv2$

$\displaystyle\implies4k\equiv-1\pmod5\equiv4\implies k\equiv1$ as $(4,5)=1$

$\displaystyle\implies(1-10)^{2k}\equiv1-20\cdot1\equiv81\pmod{100}$

$\displaystyle\implies3^{3^{(4b+3)}}\equiv27\cdot81\pmod{100}\equiv?$