欧拉定理(欧拉函数)

设 $R=\{r_1,\dots,r_{\varphi(n)}\}$ 为模 $n$ 中与 $n$ 互素的剩余。乘以 $a$ 是 $R$ 上的一个置换(由 $\gcd(a,n)=1$)。在置换前后把 $R$ 中所有元素相乘得 $a^{\varphi(n)}\prod r_i \equiv \prod r_i \pmod n$;消去 $\prod r_i$(模 $n$ 可逆)后即得 $a^{\varphi(n)}\equiv1\pmod n$。