费马小定理证明快速幂求逆元()-其他

费马小定理证明快速幂求逆元()

费马小定理： $p$为质数， $a$ 为任意自然数，且不存在 $a\ |\ p$ 则

$a^p\equiv a(mod\ \ p)$

证明：

显然当 $ a\ =\ 1$ 的时候成立，此时$1\equiv 1(mod\ \ p)$

假设 $p\ |\ (a^p-a)$

考虑 $(a+1)^p-(a+1)$

$=\ \sum\limits_{k=0}^{p}\ C_{p}^{k}a^k-a-1$

$=\ \sum\limits_{k=1}^{p-1}\ C_{p}^{k}a^k+a^p-a$

易知$C_{p}^{k}= \frac{P!}{k!*(p-k)!}$

即$p\ |\ \sum\limits_{k=1}^{p-1}C_{p}^{k}$ ，又 $p\ |\ (a^p-a)$

所以 $p\ |\ (a^{p+1}-(a+1))$

根据数学归纳法可得$a^p\equiv a(mod\ \ p)$

即$a^{p-1}\equiv 1(mod\ \ p)$ ，$a*a^{p-2}\equiv 1(mod\ \ p)$

又$a*a^{-1}\equiv 1(mod\ \ p)$

所以 $a^{p-2}$ 为 $a$ 在模 $p$ 意义下的逆元

————————