完全剩余系与简化剩余系

模 $n$ 把整数切成 $n$ 个同余类。完全剩余系是把每一类各挑一个代表；简化剩余系再加一道筛：只留和 $n$ 互素的那些类。两套对象看起来只是「选代表」，真正管的却是后面几乎所有乘法论证：平移会不会丢类、互素倍乘会不会重排、以及为什么可逆元恰好有 $\varphi(n)$ 个。下面把定义、两条定理和欧拉函数放在一起，手算和代码对得上即可。

完全剩余系

固定正整数 $n$。一组整数

叫做模 $n$ 的完全剩余系，如果它们两两模 $n$ 不同余。换句话说，这 $n$ 个数恰好落在 $n$ 个不同的同余类里，每一类一个。

最常用的两组是

前者常叫最小非负完全剩余系。奇数模还可以取对称的一组：

判定不必真的列出余数表。只要确认两件事：一共 $n$ 个数，并且任意两个差不被 $n$ 整除。个数对了、两两不同余，就自动覆盖全部同余类——因为同余类总共只有 $n$ 个，装进 $n$ 个互异的盒子里，只能是每盒恰好一个。

等价说法还有两种，用起来更方便。其一：把每个 $a_i$ 换成 $a_i\bmod n$，得到的恰好是 $\{0,1,\dots,n-1\}$ 的一个排列。其二：任意整数 都和其中恰好一个 同余。三种表述一样，证明里常在「两两不同余」和「覆盖全部」之间切换。

代表可以取得很野。$\{12,-3,22,7\}$ 模 $4$ 分别是 $0,1,2,3$，因此也是完全剩余系。关键从来不是数本身小不小，而是它们落在哪些类里。

简化剩余系

完全剩余系里，有的代表和 $n$ 互素，有的不互素。把不互素的丢掉，剩下的叫做模 $n$ 的简化剩余系（也叫既约剩余系）。

更干净的定义不依赖先取完全剩余系：一组整数

是模 $n$ 的简化剩余系，当且仅当

• 每个 $r_i$ 都满足 $\gcd(r_i,n)=1$；
• 它们两两模 $n$ 不同余；
• 个数 恰好等于与 互素的同余类个数。

这个个数记作 $\varphi(n)$，即欧拉函数。于是任何简化剩余系都恰好有 $\varphi(n)$ 个元素。标准取法是

例如 $n=8$ 时，$\varphi(8)=4$，简化剩余系可以取 $\{1,3,5,7\}$。$n=9$ 时，，可以取 。注意 永远不在简化剩余系里——除非 这种平凡情形。 时 ，零类没有乘法逆。

同一套简化剩余系可以换代表。$\{9,11,13,15\}$ 模 $8$ 仍是 $\{1,3,5,7\}$，所以也是简化剩余系。换代表的合法操作是对单个元素加上 $n$ 的倍数；对整组加同一个与 $n$ 无关的常数，互素性一般会坏掉。下一节平移定理会把这件事说清楚。

简化剩余系对应的是环 $\mathbb{Z}/n\mathbb{Z}$ 里的乘法可逆元，也就是单位群 $(\mathbb{Z}/n\mathbb{Z})^\times$。后面倍乘定理会用到这一点：和 $n$ 互素，等价于模 $n$ 有逆元。完全剩余系描述加法上的「满席」，简化剩余系描述乘法上的「可逆席」。

平移之后仍是完全剩余系

定理。 设 $a_1,\dots,a_n$ 是模 $n$ 的完全剩余系，$b$ 是任意整数。则

仍是模 $n$ 的完全剩余系。

证明。 个数仍是 $n$。若某两个平移后同余，

两边减 $b$，得到 $a_i\equiv a_j\pmod n$。原来是完全剩余系，故 $i=j$。于是平移后仍然两两不同余，结论成立。

直观说法是：每个同余类同时加 $b$，只是把标签转了一圈，没有两堆并成一堆，也没有空出一堆。映射 $x\mapsto x+b$ 在模 $n$ 的同余类上是双射，所以把一套完全代表送成另一套完全代表。

也可以先取模再看。设 $a_i\equiv i-1\pmod n$ 是最小非负那一组，则 $a_i+b\equiv (i-1+b)\bmod n$，不过是把 循环移位，当然还是完全剩余系。一般的完全剩余系只是这组的重排，结论一样。

平移不保简化剩余系。$\{1,3,5,7\}$ 是模 $8$ 的简化剩余系，每个加 $1$ 变成 $\{2,4,6,8\}$，四个数都和 $8$ 不互素。加一个常数会改变「是否与模互素」这件事，所以简化剩余系没有一般的平移定理。只有极特殊的 偶尔还能留下 个互素类，不能当定理用。

倍乘之后何时仍是剩余系

定理。 设 $a_1,\dots,a_n$ 是模 $n$ 的完全剩余系。若 $\gcd(c,n)=1$，则

仍是模 $n$ 的完全剩余系。

证明。 个数仍是 $n$。若 $ca_i\equiv ca_j\pmod n$，则 $$ 整除 。因为 ， 与 没有公共素因子，故 必须整除 ，即 。原来两两不同余，所以 。

条件 $\gcd(c,n)=1$ 不能少。若 $d=\gcd(c,n)>1$，则每个 $ca_i$ 都是 的倍数，倍乘后的数只能落在模 下 的倍数那几类里，覆盖不满 类，当然不是完全剩余系。更定量地说，像的个数是 ：同一个余数会重复 次。模 乘 只剩 四类，每类出现两次，就是这个计数。

证明里真正用到的是「$c$ 可以约掉」。$n\mid c(a_i-a_j)$ 且 $\gcd(c,n)=1$，于是 。若 与 有公约数，这一步就不成立， 撞车也无法回溯到 撞车。

简化剩余系有平行的一条。

定理。 设 $r_1,\dots,r_{\varphi(n)}$ 是模 $n$ 的简化剩余系。若 $\gcd(c,n)=1$，则

仍是模 $n$ 的简化剩余系。

证明。 先看互素：$\gcd(c,n)=1$ 且 $\gcd(r_i,n)=1$，故 $\gcd(cr_i,n)=1$。再看两两不同余：若 ，同样用 推出 ，从而 。个数仍是 ，三件事齐了。

也可以从可逆元来看。$c$ 模 $n$ 可逆，乘 $c$ 是 $(\mathbb{Z}/n\mathbb{Z})^\times$ 上的双射，只是把简化剩余系重新排列。

两条倍乘定理合在一起，常用推论是：对任意与 $n$ 互素的 $c$，以及任意完全（或简化）剩余系 $\{a_i\}$，集合 $\{ca_i\bmod n\}$ 只是原集合的一个置换。

和 $\varphi(n)$ 的关系

$\varphi(n)$ 可以就定义为「模 $n$ 的简化剩余系里有几个数」。标准公式

说的是同一件事：先有 $n$ 个同余类，再按素因子把不互素的类剔掉。

几个常用值要记熟。$p$ 为素数时 $\varphi(p)=p-1$，简化剩余系就是 $\{1,2,\dots,p-1\}$。$p^k$ 时 ，去掉 的倍数即可。若 互素，则 。合数模要把公式乘开，不要看见 就抄上去。

公式可以从完全剩余系读出来。最小非负完全剩余系有 $n$ 个数。对每个素因子 $p\mid n$，其中 $p$ 的倍数占 $1/p$，留下比例 $1-1/p$。不同素因子对应的「被 $p$ 整除」可以一起筛，乘积就是 。所以 不是外加的计数函数，它就是「从完全剩余系里抽出简化剩余系」的那次筛选。

欧拉定理是简化剩余系最直接的应用。设 $\gcd(a,n)=1$，$r_1,\dots,r_{\varphi(n)}$ 是一组简化剩余系。由倍乘定理， 也是简化剩余系，因此两边的乘积模 相同：

每个 $r_i$ 都和 $n$ 互素，乘积也可逆，两边约掉后得到

这里用到的不是「怎么解同余方程」，而是：互素倍乘只是把简化剩余系重排。$\varphi(n)$ 既是元素个数，也是这个乘法群的阶。

另一件小事：完全剩余系永远是 $n$ 个，简化剩余系永远是 $\varphi(n)$ 个。$\varphi(n)=n-1$ 当且仅当 $n$ 为素数；$n$ 合数时两者差得很多。$n=8$ 时一边 个、一边 个，不能混着数。

手算例子

例一：模 $7$ 的两套代表

$\{0,1,2,3,4,5,6\}$ 是完全剩余系。$7$ 是素数，$\varphi(7)=6$，简化剩余系是 $\{1,2,3,4,5,6\}$。

平移 $10$：$\{10,11,12,13,14,15,16\}$，模 $7$ 依次是 $\{3,4,5,6,0,1,2\}$，仍覆盖全部。倍乘 ：，模 是 ，也是完全剩余系。简化剩余系乘 得到 ，正好是原来六个可逆类的重排。

例二：模 $8$，倍乘会失败

完全剩余系取 $\{0,1,2,3,4,5,6,7\}$，简化剩余系取 $\{1,3,5,7\}$。

乘 $3$（与 $8$ 互素）：

八个数互异，仍是完全剩余系。简化的四个变成

仍是 $\{1,3,5,7\}$。

乘 $2$（与 $8$ 不互素）：

只剩偶数类，重复出现，不是完全剩余系。简化剩余系乘 $2$ 得到 $\{2,6,2,6\}$，既有重复，又全不与 $8$ 互素。

例三：用 $\varphi$ 核对个数

$n=15$，$\varphi(15)=\varphi(3)\varphi(5)=2\cdot 4=8$。标准简化剩余系是

一共八个，和公式一致。$\{0,1,\dots,14\}$ 是完全剩余系，十五个数。把其中与 $15$ 不互素的 $0,3,5,6,9,10,12$ 去掉，剩下的正好是上面那八个。

乘 $4$（$\gcd(4,15)=1$）后，这八个数变成

仍是同一集合。乘 $5$ 则全部变成 $0$ 或 $5$ 或 $10$，立刻塌缩。

例四：对称完全剩余系

模 $9$ 的对称完全剩余系是 $\{-4,-3,-2,-1,0,1,2,3,4\}$。平移 $4$ 得到 $\{0,1,2,3,4$，正是最小非负那一组，定理说这必然发生。其中与 互素的是 ，模 即 ，和标准简化剩余系 相同，个数 。

若把对称的九个数整体加 $1$，得到 $\{-3,-2,-1,0,1,2,3,4,5\}$，仍是完全剩余系；其中与 $9$ 互素的是 $\{-2,-1,1,2,4$。和上一组 相比，丢掉了 （平移后变成 ，能被 整除），新进来 。个数碰巧还是 ，集合已经换了。这说明：平移后的完全剩余系可以立刻用，简化剩余系必须重新筛一遍，不能继承旧名单。

用 Python 构造

完全剩余系几乎不用构造：range(n) 就是最小非负那一组。简化剩余系按定义筛一遍即可；若只要个数，用欧拉函数的乘积公式更快。

reduced_residues 对 $n>1$ 会自动跳过 $0$，因为 $\gcd(0,n)=n\neq 1$。is_complete 和 is_reduced 都先取模再比集合大小，避免「看起来有 $n$ 个数、模完却撞车」这种假阳性。

筛简化剩余系是 $O(n\log n)$（每个数一次 $\gcd$）。只要个数时用 euler_phi，复杂度是试除到 $\sqrt{n}$。需要很多组随机代表时，可以先取出标准简化剩余系，再对每个元素加同一个 $$，得到的仍是简化剩余系——这是「同一类换一个代表」，不是前面那个对整个集合做平移。

容易踩的坑

完全剩余系看个数是不是 $n$，简化剩余系看个数是不是 $\varphi(n)$。把 $\{1,2,\dots,n-1\}$ 当成任意 $n$ 的简化剩余系，只在 $n$ 为素数时成立。 时 必须拿掉。

倍乘定理的前提是 $\gcd(c,n)=1$，不是「$c$ 不等于 $0$」。模 $12$ 乘 $5$ 可以，乘 $2$、乘 $$、乘 都会塌缩。写代码时若只判断 ，后面的置换论证全是错的。

平移保完全剩余系，不保简化剩余系。想换简化剩余系里某个数的代表，应当对单个元素加 $n$ 的倍数，而不是对整组加同一个与 $n$ 无关的常数。

取模之后才谈「是不是同一组」。$\{1,3,5,7\}$ 和 $\{9,11,13,15\}$ 模 $8$ 是同一套简化剩余系，后者只是代表换了。比较两个剩余系，应比较 $\{a\bmod n\}$ 做成的集合，不要直接比列表。

$\varphi(n)$ 的实现不要写成「从 $1$ 数到 $n$ 数互素的有几个」还以为自己在算公式。枚举是对的，但和乘积公式是两条路；对大 $n$ 只问个数时，试除素因子更合适。还要注意 $\varphi(1)=1$，标准简化剩余系是 $\{0\}$ 或 （两者同余），不要对 特判成空集。

列表里有重复，取模前看不出来。$\{1,9,17\}$ 三个数互不相同，模 $8$ 却都是 $1$，既不是完全剩余系的一部分，更不是简化剩余系。写入集合前先 % n。

最后，剩余系是代表元的集合，不是某个方程的解集。它回答的是「模 $n$ 有哪些类、哪些类可逆」，以及这些类在平移、互素倍乘下如何走动。把「选代表」和「求解」分开，后面做欧拉定理、原根和乘法阶时才不会把个数数错。