剩余系：把无穷多个整数装进有限个抽屉

模 $m$ 的余数有 $m$ 种：$0,1,\dots ,m-1$。任取 $m$ 个整数，如果它们模 $m$ 的余数两两不同，就称这 $m$ 个数构成模 $m$ 的一个完全剩余系。

最标准的一组是 $0,1,2,\dots ,m-1$。但 $1,2,\dots ,m$ 也是，$-3,-2,-1,0,1$（$m=5$ 时）也是。

这条性质是欧拉定理和威尔逊定理的源头。

在 $0,1,\dots ,m-1$ 里，与 $m$ 互素的那些数，构成简化剩余系。它的元素个数记作 $\phi (m)$，叫欧拉函数。

• $m$ 是素数 $p$：$\phi (p)=p-1$
• $m=p^k$：$\phi (p^k)=p^k-p^{k-1}$
• $m=ab$ 且 $gcd(a,b)=1$：$\phi (ab)=\phi (a)\phi (b)$

若 $gcd(a,m)=1$，则

证明思路：把简化剩余系 $r_1,\dots ,r_{\phi (m)}$ 全部乘 $a$，得到的集合还是简化剩余系（同样是置换），所以两个集合的乘积同余：

两边约掉与 $m$ 互素的乘积，得证。

例1 验证置换

$m=7$，取 $a=3$。写出 $3\times 0,3\times 1,\dots ,3\times 6$ 模 $7$ 的余数。

解：$0,3,6,2,5,1,4$，正好是 $0$ 到 $6$ 的一个排列，确实是完全剩余系。

例2 用欧拉定理降次

求 $3^{100}$ 除以 $7$ 的余数。

解：$\phi (7)=6$，$gcd(3,7)=1$，由欧拉定理 $3^6\equiv 1$。

$100=6\times 16+4$，故 $3^{100}\equiv 3^4=81\equiv 4\left(\mathrm{mod}7\right)$。

例3 威尔逊定理

设 $p$ 是素数，证明 $(p-1)!\equiv -1\left(\mathrm{mod}p\right)$。

解：$1,2,\dots ,p-1$ 中，每个数 $a$ 都有唯一的逆元 $a^{-1}$（模 $p$），且 $a·a^{-1}\equiv 1$。

逆元等于自身的只有 $a=1$ 和 $a=p-1$（因为 $a^2\equiv 1$ ⇒ $(a-1)(a+1)\equiv 0$ ⇒ $a\equiv \pm 1$）。

其余 $p-3$ 个数两两配对，每对乘积 $\equiv 1$。所以 $$(p-1)!\equiv 1·(p-1)·1\cdots 1\equiv -1\left(\mathrm{mod}p\right)$$

反过来也成立：若 $(n-1)!\equiv -1\left(\mathrm{mod}n\right)$，则 $n$ 是素数。这条常用来判素数。

例4 求 φ

求 $\phi (100)$ 与 $\phi (360)$。

解：$100=2^2·5^2$，$\phi (100)=100\times \frac{1}{2}\times \frac{4}{5}=40$。

$360=2^3·3^2·5$，$\phi (360)=360\times \frac{1}{2}\times \frac{2}{3}\times \frac{4}{5}=96$。

公式：$\phi (n)=n{\prod }_{p\mid n}(1-\frac{1}{p})$，$p$ 取遍 $n$ 的不同素因子。

例5 逆元

求 $7$ 在模 $11$ 下的逆元。

解：试乘：$7\times 1=7$，$7\times 2=14\equiv 3$，$7\times 3=21\equiv 10$，$7\times 4=28\equiv 6$，$7\times 5=35\equiv 2$，$7\times 6=42\equiv 9$，$7\times 7=49\equiv 5$，$7\times 8=56\equiv 1$。

所以逆元是 $8$。也可以直接用欧拉定理：$7^{10}\equiv 1$，故 $7^{-1}\equiv 7^9$。