@ssrivastava990

I have used the following property:

If A is co-prime to p and \phi(p) is the number of numbers less than p and co-prime to p then, A^{\phi(p)} \equiv 1 \pmod p. The proof can be found here

We can write any number k as k = q\cdot \phi(p) + r where \displaystyle q = \left \lfloor\frac{k}{\phi(p)} \right\rfloor and r = k \% \phi(p)

Then, \displaystyle A^k = A^{q\cdot \phi(p) + r} = A^{q\cdot \phi(p)}\cdot A^{r} = \left ( A^{q} \right )^{\phi(p)}\cdot A^{r}

Since A is co-prime to p, A^q is also co-prime to p \therefore \left ( A^{q} \right )^{\phi(p)} \equiv 1 \pmod p

\therefore A^k \equiv A^{k \% \phi(p)} \pmod p

If you are unfamiliar with the mod notation read this