I want to calculate (a ^ (b^c) )% m , So I am using pow(a, pow(b,c,m),m) where pow(a,b,m) is (a^b)%m,But people are using pow(a, pow(b,c,**m-1**),m).

Why **m-1 not m**?

I am solving http://www.codechef.com/problems/IITK2P10

They are using the Fermat’s Little Theorem.

a^{p-1} \equiv 1 \pmod m

Therefore,

Let

b^c = Q*(m-1)+R

where, Q is the quotient and R is the remainder

Therefore,

a^{b^c} \equiv (a^{m-1})^Q.a^R \pmod m

\equiv 1^Q*a^R \pmod m

\equiv a^{b^c \% (m-1)} \pmod m

Hope this helps.

2 Likes

Everything is right about above approach except that it is applicable for all m.

It’s applicable only when m is prime.

If m is not prime you need to find Euler Totient function for m then do b^c mod n where

n=Euler Totient(m). n = m-1 only when m is a prime number.

Now compute a^(b^c mod n) mod m . This will give you the required result.