Sonic_AR's blog

A^B^C mod prime [how to solve it]
By Sonic_AR, history, 4 years ago, In English

I have found that the answer to my question is

a^((b^c) % prime — 1) % prime

But I don't know a proof, can anyone tell me the proof or give me a tutorial to read it. Thanks

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

Comments Comments (5)
| Write comment?
»
4 years ago, # |
← Rev. 14   Vote: I like it +30 Vote: I do not like it

Fermat's little theorem states that for a prime $$$p$$$ and any integer $$$a$$$ such that $$$0 < a < p$$$,

$$$ a^{p-1} \equiv 1 \implies a^b \equiv a^{b \bmod {p-1}} \pmod{p} $$$

In other words, the powers of $$$a$$$ modulo $$$p$$$ repeat with a period of $$$p-1$$$.

This is further generalized by Euler's theorem which implies the powers of $$$a$$$ repeat with a period of $$$p-1$$$. This can be even further generalized with Lagrange's theorem for groups.

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

    Actually, $$$a$$$ can be greater than $$$p$$$. but the condition is $$$a,p$$$ are relatively prime.

    $$$\textbf{gcd}(a,p) = 1 \implies a^{p-1} \equiv 1 \pmod{p}$$$

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

https://www.geeksforgeeks.org/find-abm-where-b-is-very-large/

You can use above link for better understanding.

→ Reply
»
12 days ago, # |
  Vote: I like it -44 Vote: I do not like it

It can be shown that prime = 2,3,5,7 all works. For every prime > 2,3,5,7 it can be represented by 2,3,5,7, so the answer is 1*1*1*...*1=1.

→ Reply