i was using modpower(a,b,mod) to calculate a^b and got correct answer in CSES exponentation 1(problem), but in exponentiation 2(the other problem) i have to calc. a^(b^c) and then i used the same func like —> modpow(a, modpow(b,c,mod), mod) but it is WA then when i was searching for some answer i found out this works…
modpow(a, modpow(b,c,mod-1), mod) …
but need to know why exactly? any explanation appereciated. 
1 Like
Fermat’s Little Theorem
a^(p-1) mod p = 1 , where p is prime.
so, a^ (b^c) = a ^ ( (b^c) mod p-1 ) mod p
Ok firstly tell me, why do you believe that a^{b^c \mod p} = a^{b^c} \mod p.
That is not true. You cannot just take mod everywhere.
What we can show is a^{p-1} \equiv 1\mod p. Therefore we will be able to show that a^{b^c} \equiv a^{b^c \mod p-1} \mod p.
There is a proof too, but it is quite advanced.
Proof
There is infact a general theorem. a^{\phi(n)} \equiv 1 \mod n, where \phi(n) is the number of numbers x such that 0<x<n and gcd(x,n) = 1 if a is coprime to n
Let us create a graph with V as the set of possible values of x. Let us create an edge from all vertices x \in V to x\times a \mod n. This must be in the set V as a and x are coprime to n.
It is obvious from definition that all nodes have exactly one outgoing edge. Let us show that each node has exactly one incoming edge. Since gcd(a,n) = 1, there exists a^{-1} such that a \times a^{-1} \equiv 1 \mod n.
Let us say there are 2 values x,y \in V such that ax = ay \mod p. That would imply x \equiv y \mod n, as a^{-1} exists.
Knowing the fact that each vertex has exactly one incoming and one outgoing edge, We can deduce that the graph is composed of disjoint simple cycles.
Let us now prove that there cannot exist 2 cycles of different length. Let C be the set of cycles.
Let us define k as the smallest value such that k>0 and a^k \equiv 1 \mod n. This must exist as the graph is a set of disjoint simple cycles.
It is easy to see that each cycle will be of length k. We can prove that it cannot be more, as we know that we will cycle within k steps, and it cannot be less, as that implies k is not the minimal such value.
Let C be the number of cycles. We can deduce that kC = |V| = \phi(n).
Therefore a^{\phi(n)} \equiv a^{kC} \equiv (a^k)^C \equiv 1 \mod n.
4 Likes
ohh now when u write it this way i realize this …thanks @everule1 @not_abhishek
still need to go through the proof etc to get a better understanding 
thanks i will look at it in the morning
1 Like