【acm】【数论】费马小定理：求逆元与降幂

定义

若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