费马小定理

考虑模$p$的非零剩余集合$S=\{1,2,\dots,p-1\}$,以及把$S$中每个元素送到某个剩余的映射$x \mapsto ax \bmod p$。

该映射在$S$上是单射的:若对$x,y\in S$有$ax\equiv ay\pmod p$,由于$\gcd(a,p)=1$,消去律(前一主题已证明)给出$x\equiv y\pmod p$,从而$x=y$,因为二者都属于$\{1,\dots,p-1\}$。同样对$x\in S$, $ax$ 也不会 $\equiv 0\pmod p$,因为$p$是素数且不整除$a$也不整除$x$。所以该映射确实又落回$S$中。

有限集合$S$到自身的单射映射自动是双射。因此$\{a\cdot1,a\cdot2,\dots,a\cdot(p-1)\} \pmod p$不过是$\{1,2,\dots,p-1\}$按另一种顺序排列而已。

把两个集合的全部$p-1$个元素分别相乘。一边得到$(a\cdot1)(a\cdot2)\cdots(a\cdot(p-1)) = a^{p-1}\,(p-1)!$;另一边由于只是同样的数重新排列,恰好得到$(p-1)!$。于是$a^{p-1}(p-1)! \equiv (p-1)! \pmod p$。

因为$p$是素数,$1,2,\dots,p-1$中没有一个能被$p$整除,故$\gcd((p-1)!,p)=1$。再次应用消去律从两边约去公因子$(p-1)!$,得到$a^{p-1}\equiv1\pmod p$。$\blacksquare$

(群论重述:由于$p$是素数,非零剩余在乘法下构成一个阶为$p-1$的群,而拉格朗日定理指出任何元素的阶——这里指使$a^k\equiv1$成立的最小$k$——必须整除群的阶$p-1$;因此自动有$a^{p-1}\equiv1\pmod p$。)