In Wikipedia, Graham's number, it is described how to calculate the last d digits of Graham's number. They introduce an algorithm simply iterating
$$x = 3^x \mod 10^d$$
d times starting with x=3.
What slightly confuses me : To calculate a power $a^b \mod n$ , $a$ must be reduced mod $n$, but $b$ must be reduced mod $\phi(n)$.
As, for example $\phi(1000)=400$ , reducing modulo $1000$ and reducing modulo $400$ is the same, if only the last TWO digits have to be calculated. Is this the reason, that the height of the power tower must be by one greater than the number of digits to calculate ? Or did I miss something else ?
To generalize the problem. How do I properly calculate
$$a \uparrow \uparrow b \mod n$$
for natural numbers $a$, $b$, $n$ ?
This follows from the Euler-Fermat theorem, which says that $$a^{\phi(n)}\equiv 1\mod n$$ if $\gcd(a,n)=1$.
Thus, in the exponent, we may work $\mod \phi(n)$, because $$a^{k}=a^{k-\phi(n)}a^{\phi(n)}\equiv a^{k-\phi(n)}\mod n$$ To calculate $a\uparrow\uparrow b$, simply work up the chain of powers, so for $a^{b^c}\mod n$, you may work modulo $ n$ for $a$, modulo $\phi(n)$ for $b$ and modulo $\phi(\phi(n))$ for $c$. This continues for higher power towers. Because $\phi(n)<n$ for all $n>1$, we know that eventually, we will work $\mod 1$ at some (high enough) place in the power tower, and therefore from that moment on, all exponents will be $1$.
EDIT
In the algorithm given at the wikipedia page, the result is evaluated modulo $10^d$ each time. The third or so post in this link by Jacques explains why.