欧拉降幂

\(f(x)=\left\{ {\begin{array}{}a^b\equiv a^{b \mod \phi(p) }(mod\ p,gcd(a,p)=1)\\a^b\equiv a^b(mod\ p,b<\phi(p))\\a^b\equiv a^{b\%\phi(p)+\phi(x)} (mod\ p,b\ge \phi(p))\end{array}} \right.\)

第一个公式主要根据欧拉定理：

\(a^{\phi(p)}\equiv1(mod \ p,gcd(a,p)=1)\)

第二个不用说。

第三个证明：

参考：https://www.cnblogs.com/cglongge/p/11194968.html

具体证明后期补（摸鱼）。

广义欧拉降幂

原文：https://www.cnblogs.com/redegg/p/11746928.html