定义
若p为素数， (a, p) = 1, 则
证明
引理1 若(a, m) = 1, 则
的最小剩余(mod m) 按某种次序排列后为
tips
关于引理1的证明不作赘述，主要是证明两两的最小剩余不重复，使用反证法即可。
有了引理1，即可证明费马小定理，证明如下。
由引理1易知
求逆元
见 乘法逆元: 扩展欧几里德 费马小定理 递推 带余数同余式的一般解法
降幂
推论 若p为素数， 则对一切a，都有
tips
注意这里是一切a，即a和p不一定互素。
当指数比较大的时候，可以使用下面的公式进行降幂。
若p为素数，且p不能整除a(或能整除则结果为0)，有
下证此式。
设如下变量:
例题
Sum HDU - 4704
M斐波那契数列 HDU - 4549
