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?

1 Like

Hi you can see the proof here

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).