How to solve a^(b^c) % M

I did it using modulo exponentiation like this:

say, f(a,b) returns a^b % m (AC)

Then answer will be f(a,f(b,c)) (WA)

But this method gives WA.

(PS: a,b,c are of order 1e9, m is 1e9+7)

I think a^b^c % M is not equal to (a^(b^c)%M)%M, This is where I might be wrong…

Since a^{p-1} = 1 (mod p), when p is a prime (by Fermat’s theorem), so, a^b (mod p) = a^{b mod(p-1)} (mod p). So, first compute d = b^c mod(M-1) and then compute a^d (mod M). That will be the answer.

3 Likes

Since gcd(a,m) is 1.
Please refer Euler’s theorem.
This will be general solution.
Many people have myth that we can always modulo with m-1
Though we can when m is prime.

1 Like

I didn’t get how a^b = a^bmod(p−1)

It’s special case of Euler’s theorem.

1 Like

Oh, Ok then, I’ll go learn euler’s theorem first… Any good resource you know of?

1 Like