In this question http://www.codechef.com/WPC1501/problems/IITK2P10
and soln http://www.codechef.com/viewsolution/5957683 i am confused why mod-1 is used?
Can anyone make me understand the concept?
in short
Can you please help me in proving that (k^(2^n))MOD is equailvalent to (k^((2^n)(MOD-1))%MOD?
a^b^c = a^((b^d)mod phi(m))mod m , where d = c mod phi(phi(m))) where phi of m is the number of integers less
then equal to m which are co-prime to m i.e -> gcd( x , m ) = 1 , 1 <= x <= m ,here m is prime , therefore
phi(m) = m-1
a^b^c = a^((b^d) mod (m-1)) mod m and d = c mod phi( m - 1).
thanks a lot mate