1
$\begingroup$

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$ ?

$\endgroup$
  • $\begingroup$ Link is probably en.wikipedia.org/wiki/… $\endgroup$ – Henry Jan 2 '14 at 15:00
  • $\begingroup$ Exactly that, you may add the link because I do not know how to do that. $\endgroup$ – Peter Jan 2 '14 at 15:02
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you, so it is more difficult than it seems at first sight. $\endgroup$ – Peter Jan 2 '14 at 15:14
  • $\begingroup$ Evaluation of power towers is never easy, but the modulo part makes sure that (even for infinite $b$), it is sufficient to reduce the tower to at least $k$ terms, where $\phi^k(n)=1$ (that is, $\phi$ applied $k$ times to $n$) $\endgroup$ – Ragnar Jan 2 '14 at 15:16
  • $\begingroup$ But what about the algorithm described in wikipedia, is it correct or not ? $\endgroup$ – Peter Jan 2 '14 at 15:16
  • $\begingroup$ I'll have a look at it $\endgroup$ – Ragnar Jan 2 '14 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.