费马小定理
定理
如果
$$
p\in \mathbb{P}\,\, \operatorname{and}\,\, p\not\mid a
$$
那么有
$$
a^{p-1}\equiv 1\pmod p
$$
证明
引理 1
若 $a\cdot c\equiv b\cdot c\pmod m$ 且 $c\perp m$，则 $a\equiv b\pmod m$。
证明 1
$a\cdot c\equiv b\cdot c\pmod m$ 可得 $(a-b)\times c\equiv 0\pmod m$，又因为 $c\perp m$，那么 $(a-b)\times c$ 当且仅当 $a-b$ 是 $m$ 的倍数即 $a-b\equiv 0\pmod m$，即可得 $a\equiv b\pmod m$。
引理 2
若 $a\perp m$，则 $\{a,2a,3a,\dots,(m-1)a\}$ 是一个模 $m$ 的完全剩余系。
证明 2
考虑使用反证法。
假设 $\exist\,i,j\in[1,m-1]\,\,\operatorname{and}\,\,i\not=j$ 使得 $i\times a\equiv j\times a\pmod m$，又因为 $a\perp m$，根据 引理 1，可得 $i\equiv j\pmod m$，而 $i,j\in[1,m-1]$，所以 $i\equiv j\pmod m$ 当且仅当 $i=j$，与假设矛盾，故得证。
由上述引理，可知 $\{1,2,3,\dots,p-1\}$ 与 $\{a,2a,3a,\dots,(p-1)a\}$ 均为模 $p$ 的完全剩余系，那么将两个集合内部元素分别相乘，可得
$$
(p-1)!\equiv(p-1)!\times a^{p-1}\pmod p
$$
又因为 $p\in\mathbb{P}$，所以 $\varphi(p)=p-1$，故可得 $p\perp (p-1)!$，根据 引理 1，两边同时约去 $(p-1)!$，可知
$$
a^{p-1}\equiv 1\pmod p
$$
证毕。