剩余系
完全剩余系与简化剩余系的构造、性质，及其在数论中的用法。
基本背景
固定一个正整数 \(m\)。若 \(m \mid a-b\)，则称 \(a\) 与 \(b\) 模 \(m\) 同余，记作
\(a \equiv b \pmod m.\)
这个关系把整数分成 \(m\) 个同余类：
\(\mathbb Z/m\mathbb Z = \{[0],[1],\ldots,[m-1]\}.\)
所谓“剩余系”，本质上就是从某些同余类中选代表元。不同剩余系的区别在于：选哪些同余类，以及代表元怎么规范化。
完全剩余系
模 \(m\) 的完全剩余系是从每个模 \(m\) 的同余类中各选一个代表所得的集合。它恰好有 \(m\) 个元素。
等价地，整数集合 \(R=\{r_1,\ldots,r_m\}\) 是模 \(m\) 的完全剩余系，当且仅当
\(r_i \not\equiv r_j \pmod m \quad (i \neq j).\)
也就是说，这些数模 \(m\) 两两不同余。
例如，模 \(5\) 时，
\(\{0,1,2,3,4\}\)
是完全剩余系，
\(\{-2,-1,0,1,2\}\)
也是完全剩余系，因为它们分别代表模 \(5\) 的五个同余类。
一个常用事实：若 \(R\) 是模 \(m\) 的完全剩余系，且 \(\gcd(a,m)=1\)，则
\(aR+b=\{ar+b:r\in R\}\)
仍是模 \(m\) 的完全剩余系。原因是乘以可逆元 \(a\) 会置换模 \(m\) 的同余类。
最小非负剩余系
模 \(m\) 的最小非负剩余系是最标准的一组完全剩余系：
\(\{0,1,2,\ldots,m-1\}.\)
每个整数 \(a\) 都唯一同余于其中某个数 \(r\)，即
\(a \equiv r \pmod m, \qquad 0 \leq r < m.\)
这个 \(r\) 称为 \(a\) 模 \(m\) 的最小非负剩余。
例如，模 \(7\) 时，
\(-3 \equiv 4 \pmod 7,\)
所以 \(-3\) 模 \(7\) 的最小非负剩余是 \(4\)。
绝对最小剩余系
模 \(m\) 的绝对最小剩余系是从每个同余类中选一个绝对值尽量小的代表。
当 \(m=2k+1\) 为奇数时，常取
\(\{-k,-k+1,\ldots,-1,0,1,\ldots,k\}.\)
例如，模 \(7\) 时可取
\(\{-3,-2,-1,0,1,2,3\}.\)
这时
\(5 \equiv -2 \pmod 7,\)
所以 \(5\) 模 \(7\) 的绝对最小剩余可写作 \(-2\)。
当 \(m=2k\) 为偶数时，端点会出现不唯一：\(k\) 与 \(-k\) 同余，且绝对值相同。例如模 \(8\) 时，
\(4 \equiv -4 \pmod 8.\)
因此偶数模下通常需要额外约定取 \(k\) 还是 \(-k\)。常见选择之一是
\(\{-k+1,-k+2,\ldots,-1,0,1,\ldots,k\}.\)
既约剩余系
模 \(m\) 的既约剩余系，也常称为缩剩余系或简化剩余系，是只从与 \(m\) 互素的同余类中各选一个代表。
换句话说，集合 \(R\) 是模 \(m\) 的既约剩余系，当且仅当：
- 对任意 \(r\in R\)，都有 \(\gcd(r,m)=1\)；
- \(R\) 中任意两个元素模 \(m\) 不同余；
- 每个与 \(m\) 互素的同余类都被 \(R\) 代表一次。
既约剩余系的元素个数是欧拉函数
\(\varphi(m)=\#\{1\leq a\leq m:\gcd(a,m)=1\} = |(\mathbb Z/m\mathbb Z)^\times|.\)
例如，模 \(10\) 的一个既约剩余系是
\(\{1,3,7,9\},\)
因为这些数都与 \(10\) 互素，并且代表所有可逆同余类。
模 \(12\) 的一个既约剩余系是
\(\{1,5,7,11\}.\)
若 \(R\) 是模 \(m\) 的既约剩余系，且 \(\gcd(a,m)=1\)，则
\(aR=\{ar:r\in R\}\)
仍是模 \(m\) 的既约剩余系。这是 Euler 定理 证明中的核心置换思想。
对比表
| 名称 | 选哪些类 | 元素个数 | 常见例子，模 \(10\) |
|---|---|---|---|
| 完全剩余系 | 所有同余类 | \(m\) | \(\{0,1,2,3,4,5,6,7,8,9\}\) |
| 最小非负剩余系 | 所有同余类 | \(m\) | \(\{0,1,2,3,4,5,6,7,8,9\}\) |
| 绝对最小剩余系 | 所有同余类 | \(m\) | \(\{-4,-3,-2,-1,0,1,2,3,4,5\}\) 或类似约定 |
| 既约剩余系 | 与 \(m\) 互素的同余类 | \(\varphi(m)\) | \(\{1,3,7,9\}\) |
记忆方式
- 完全剩余系：每个模 \(m\) 的同余类选一个代表。
- 最小非负剩余系：完全剩余系的标准版本，代表元在 \(0\) 到 \(m-1\) 之间。
- 绝对最小剩余系：代表元尽量靠近 \(0\)。
- 既约剩余系：只保留与 \(m\) 互素的那些类，也就是 \((\mathbb Z/m\mathbb Z)^\times\) 的代表元。