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.