iit kanpur

general
,
1

In this question CodeChef: Practical coding for everyone
and soln CodeChef: Practical coding for everyone 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
2

Hi you can see the proof here

3

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

4

thanks a lot mate