欧拉定理

设$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)$。