Let's suppose I need to calculate $$$a^{b^{c}}$$$ modulo $$$10^9 + 7$$$, with the constraints $$$1 \leq a, b, c \leq 10^{18}$$$. I can calculate $$$ans = b^c$$$ in $$$\mathcal{O}(log(c))$$$, with modulo $$$10^9 + 6$$$, (probably everyone knows how) and then calculate $$$a^{ans}$$$ with modulo $$$10^9 + 7$$$.
But how does first taking $$$10^9 + 6$$$ and then $$$10^9 + 7$$$ work? Can anyone present a formal proof for this? Also are there any other methods to do this?
Check this: Fermat's Little Theorem
According to Fermat's Little Theorem, for some prime $$$p$$$
$$$a ^ {p - 1} \equiv 1 \pmod p $$$
Now suppose we have to find $$$ a ^ {x} \pmod p $$$ We can write $$$x$$$ as $$$k * (p - 1) + r$$$ where $$$r$$$ is the remainder when we divide $$$x$$$ by $$$p - 1$$$ for some constant $$$k$$$
$$$ a ^ {x} = a ^ {k * (p - 1) + r} \pmod p $$$
$$$ a ^ {k * (p - 1) + r} = a ^ {{(p - 1)} * {k}} * a ^ {r} \pmod p$$$
$$$a ^ {{(p - 1)} * {k}} * a ^ {r} = 1 ^ {k} * a ^ {r} \pmod p $$$ Since $$$a ^ {p - 1} \equiv 1 \pmod p $$$
Hence
$$$ a ^ {x} \equiv a ^ {r} \pmod p $$$ where $$$r = x$$$ % $$$(p - 1)$$$
Ohh understood it. Should have tried and figured it out myself, but thank you anyways for the good explanation.
To check your understanding you can try a slightly harder variant. Suppose the height of the tower of powers can be more than two. How can we go about solving it. Ex : $$$ a ^ {b ^ {c ^ {d}}} \pmod p$$$ and so on for some variable height n.
Till now I could only figure out how to solve for a particular MOD, by calculating the Euler Totient function for each of the residual MODs. Is there a more general method? Can you point out some problem where I can use this?
you need to calculate the totient function for every mod (just note that it is not always $$$p-1$$$...). However, Fermat's little theorem can only be applied directly if the mod is prime.
This problem asks for something similar: https://open.kattis.com/problems/exponial
Thank you for the problem. However this problem has an additional challenge that the given number is also too large for direct iteration, so I believe that some other trick is going to be used here. I will try to solve it anyways though.
and how do you calculate it with 10^9 + 6?
do you mean to ask, "how do you calculate it with 10^9+6 base for the fourth power"?
Yep
upd: I read blog post wrong oops