费马小定理

---

费马小定理：假如 $a$ $a$ 是一个整数，$p$ $p$ 是一个质数，那么 $a^p-a$ $a^p-a$ 是 $p$ $p$ 的倍数，可以表示为

如果 $a$ $a$ 不是 $p$ $p$ 的倍数，这个定理也可以写成

证明

因为 $(a,p)=1$ $(a,p)=1$，取整数集 $A$ $A$ 为 {$1,2,3,...,p-1$ $1,2,3,...,p-1$} ，$B$ $B$ 是 $A$ $A$ 中所有元素乘以 $a$ $a$ 得到的集合 $B=\{1\ast a,2\ast a,3\ast a,...,(p-1)\ast a\}$ $B=\left\{1*a,2*a,3*a,...,(p-1)*a \right\}$ 对 $B$ $B$ 中所有的数除 $p$ $p$ 得到余数 $r_1,r_2,r_3,...,r_{p-1}$ $r_1,r_2,r_3,...,r_{p-1}$，则集合$\{r_1,r_2,r_3,...,r_{p-1}\}$ $\left\{r_1,r_2,r_3,...,r_{p-1} \right\}$为集合$\{1,2,3,...,p-1\}$ $\left\{1,2,3,...,{p-1} \right\}$的重新排列。即 $1,2,3,...,p-1$ $1,2,3,...,{p-1}$ 在余数中恰好各出现一次；这是因为对于任两个相异 $k\ast a$ $k*a$ 而言$（k=1,2,3...,p-1)$ $（k=1,2,3...,p-1)$，其差不是 $p$ $p$ 的倍数（所以不会有相同余数），且任一个 $k\ast a$ $k*a$ 亦不为 $p$ $p$ 的倍数（所以余数不为0）。因此得到

即

在这里 $W=1·2·3·····(p-1)$ $W=1·2·3·····(p-1)$，且 $(W,p)=1$ $(W,p) = 1$，因此将整个公式除以 $W$ $W$ 即得到： ​ $a^{p-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{p})$ $a^{p-1} \equiv 1\quad (\rm mod \ \ p)$

应用

实现降幂 比如求 $a^n\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{p}$ $a^{n}\ \rm mod \ p$ , $p$ $p$ 为质数 且 $(a,p)=1$ $( a,p)=1$，可以通过费马小定理实现降幂

例子 求 ${32}^{37777}\mathrm{\%}7$ $32^{37777} \% 7$，7为质数且 gcd(32,7) = 1

所以在 $p$ $p$ 为质数 且 $(a,p)=1$ $( a,p)=1$前提下