模板

费马（Fermat）小定理

当 (p) 为质数，则

(a^{p-1}equiv 1 mod p)

反之，费马小定理的逆定理不成立，这样的数叫做伪质数，最小的伪质数是341。

欧拉（Euler）定理

扩展欧拉（Euler）定理

根据扩展欧拉定理，不管a和p是不是互质，都可以缩小到 ([varphi(p),2varphi(p)]) 之间，然后暴力用快速幂求解。