【acm】【数论】费马小定理：求逆元与降幂
定义
若p为素数， (a, p) = 1, 则\[a^{p-1} \equiv 1 \pmod p \tag{1.1}\]
证明
引理1 若(a, m) = 1, 则\[a, 2a, 3a, ..., (m-1)a\] 的最小剩余(mod m) 按某种次序排列后为\[1, 2, 3, ..., m-1\]
tips
关于引理1的证明不作赘述，主要是证明两两的最小剩余不重复，使用反证法即可。
有了引理1，即可证明费马小定理，证明如下。
由引理1易知 \[a*2a*3a*\cdots*(p-1)a \equiv 1*2*3*\cdots*(p-1) \pmod p\]
即
\[a^{p-1}(p-1)! \equiv (p-1)! \pmod p\]
又\((p, (p-1)!) = 1\)，即\(p\)与\((p-1)!\)互素，则有
\[a^{p-1} \equiv 1 \pmod p\]
得证。
求逆元
见 乘法逆元: 扩展欧几里德 费马小定理 递推 带余数同余式的一般解法
降幂
推论 若\(p\)为素数， 则对一切\(a\)，都有 \[a^p \equiv a \pmod p \tag{3.1}\]
tips
注意这里是一切\(a\)，即\(a\)和\(p\)不一定互素。
当指数比较大的时候，可以使用下面的公式进行降幂。
若\(p\)为素数，且\(p\)不能整除\(a\)(或能整除则结果为0)，有
\[a^n \equiv a^{n \ mod {(p-1)}} \pmod p \tag{3.2}\]
下证此式。
设如下变量:
\[ \left\{ \begin{array}{l} k = \frac{n}{p-1} \\ b = n \pmod{ p-1 } \\ \end{array} \right. \]
即 \[ n = k \cdot (p-1) + b \]
则有
\[a^n \equiv a^{k * (p-1) + b} \pmod p\]
即 \[a^n \equiv (a^k)^{p-1}*a^b \pmod p\]
又
\[ (a^k)^{p-1} \equiv 1 \pmod p\]
所以
\[a^n \equiv a^b \pmod p\]
得证。