Modular Arithmetic

modulo

#1

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


#2

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.


#3

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.