Frankenstein123's blog

A simple Math Problem
By Frankenstein123, history, 5 years ago, In English

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?

  • Vote: I like it
  • +25
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Check this: Fermat's Little Theorem

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ohh understood it. Should have tried and figured it out myself, but thank you anyways for the good explanation.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 3   Vote: I like it +1 Vote: I do not like it

          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

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            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.

            → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

and how do you calculate it with 10^9 + 6?

→ Reply