### vignesh_in_zone's blog

By vignesh_in_zone, history, 6 weeks ago,

given three numbers p , q, r calculate the pow( p , q!) % r

It would also be helpful if you could mention the important concepts needed in solving this problem ,

• 0

 » 6 weeks ago, # |   +1 If $p$ and $r$ are relatively prime you use Euler's theorem $p^{\phi(r)} = 1$ mod $r$. So you need to calculate $q!$ mod $\phi(r)$. $\phi$ is the Euler totient function, for a prime $r$ it is just $r-1$. You can find the answer even if $(p, r) > 1$, but it involves additional steps.
•  » » 6 weeks ago, # ^ |   0 Thanks a lot, could you also mention what else do I have to learn if (p,r)>1 or will Euler totient function suffice?
•  » » » 6 weeks ago, # ^ |   0 In that case you could perform prime decomposition of $r$. Find the remainder for each prime power and then use the Chinese remainder theorem.
•  » » » » 6 weeks ago, # ^ |   0 Cant' we directly use the generalization??from this link