### GrimReaper42's blog

By GrimReaper42, history, 4 weeks ago, ,

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

• +2

 » 4 weeks ago, # | ← Rev. 14 →   +30 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.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Yeah, Fermat's Little Theorem basically finishes off this problem, since we have a period p-1, now all we need to do is find $b^c \mod p-1$ (just use binary exponentiation) and then find $a^{(\text{this number})} \mod p$. One more generalized formula is Euler's Totient Theorem, which states that $a^{\phi(x)} \equiv 1$ $(\text{mod }x)$ where $\gcd(a, x)=1$.
 » 4 weeks ago, # |   0 https://www.geeksforgeeks.org/find-abm-where-b-is-very-large/You can use above link for better understanding.