费马小定理与欧拉定理

模素数$p$的非零剩余在乘法下构成一个封闭系统:用固定的$a$乘以其中每一个,只是把它们相互打乱重排。把这种打乱重复$p-1$次,必然使每个元素都回到自己原来的位置,这正是$a^{p-1}\equiv1\pmod p$这一陈述。

考虑模$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$。)

这正是费马论证在一般模$n$下的推广:我们不再使用全体非零剩余(仅当$n$为素数时它们才在乘法下封闭),而是限制到真正与$n$互素的剩余——即拥有逆元的那些——同样的重排论证适用于这个更小、大小为$\varphi(n)$的封闭集合。

设$R=\{r_1,\dots,r_{\varphi(n)}\}$为模$n$的一个简化剩余系:每个与$n$互素的剩余类的代表元。

乘以$a$会置换$R$:对每个$r_i$,由于$\gcd(a,n)=1$且$\gcd(r_i,n)=1$(一个乘积与$n$互素当且仅当两个因子都与之互素),故$\gcd(ar_i,n)=1$,于是$ar_i \bmod n$仍属于互素剩余类;又因$\gcd(a,n)=1$,由消去律,映射$r_i\mapsto ar_i \bmod n$是单射。

有限集合$R$到自身(在剩余意义下)的单射映射即为双射,故$\{ar_1,\dots,ar_{\varphi(n)}\} \pmod n$不过是$\{r_1,\dots,r_{\varphi(n)}\}$的重新排列。

把每个集合的全部$\varphi(n)$个元素相乘:$a^{\varphi(n)}\, (r_1 r_2\cdots r_{\varphi(n)}) \equiv r_1 r_2 \cdots r_{\varphi(n)} \pmod n$。由于每个$r_i$都与$n$互素,它们的乘积$R=\prod r_i$也与之互素,即$\gcd(R,n)=1$。

从两边约去$R$(因$\gcd(R,n)=1$而有效)得到$a^{\varphi(n)}\equiv1\pmod n$。$\blacksquare$

这又是拉格朗日定理的另一种表现形式:与$n$互素的剩余在乘法下构成一个阶为$\varphi(n)$的群(单位群$(\mathbb{Z}/n\mathbb{Z})^{*}$),任何元素的阶都整除$\varphi(n)$。