密码学数学基础 笔记 4：从同余类和模运算出发，理解约消、完全剩余系、简化剩余系与欧拉函数

同余与剩余系

前面用整除、最大公因数和 Bézout 等式研究整数。固定一个正整数 $m$ 后，可以把相差 $m$ 的倍数的整数放在一起计算。这就是同余的出发点

同余与剩余类

若 $m\mid(a-b)$，称 $a,b$ 模 $m$ 同余，记为

$$a\equiv b\pmod m\quad\Longleftrightarrow\quad a-b\in m\mathbb Z$$

这也等价于 $a,b$ 除以 $m$ 得到相同的最小非负余数。例如 $-1\equiv5\pmod6$。同余满足自反、对称和传递性，因此把整数分成互不相交的剩余类：

$$[a]_m=a+m\mathbb Z=\{a+km:k\in\mathbb Z\}$$

一个类含有无穷多个整数，但模 $m$ 恰有 $m$ 个不同的类：

$$\mathbb Z/m\mathbb Z=\{[0]_m,[1]_m,\ldots,[m-1]_m\}$$

类的加法、乘法由代表元定义：

$$[a]_m+[b]_m=[a+b]_m,\qquad [a]_m[b]_m=[ab]_m$$

这些运算不依赖代表元的选择。若 $a\equiv a'$、$b\equiv b'\pmod m$，则

$$(a+b)-(a'+b')=(a-a')+(b-b'),$$

$$ab-a'b'=(a-a')b+a'(b-b'),$$

两式右侧都被 $m$ 整除。同理，同余可以代入任意整数系数多项式：$a\equiv b\pmod m$ 蕴含 $f(a)\equiv f(b)\pmod m$。这里替换的是底数；指数同余本身不能直接用于替换指数，例如 $1\equiv6\pmod5$，但 $2^1\not\equiv2^6\pmod5$

完全剩余系与约消

从每个剩余类各取一个整数，就得到模 $m$ 的一个完全剩余系（CRS）。$0,1,\ldots,m-1$ 是标准例子；任意连续 $m$ 个整数也可以。选取的代表元无需连续，例如 $\{6,14,7\}$ 模 $3$ 分别代表 $0,2,1$

模运算虽然保留加法、乘法，却不能无条件约去乘法因子。比如

$$2\cdot2\equiv2\cdot0\pmod4, \qquad 2\not\equiv0\pmod4$$

原因是 $[2]_4[2]_4=[0]_4$：非零剩余类的乘积也可能为零。设 $d=\gcd(k,m)$，正确的约消规则是

$$\boxed{ka\equiv kb\pmod m\quad\Longleftrightarrow\quad a\equiv b\pmod{m/d}}$$

证明时先将 $m\mid k(a-b)$ 同除以 $d$，再利用 $\gcd(k/d,m/d)=1$ 约去 $k/d$。特别地，若 $\gcd(k,m)=1$，模数保持为 $m$。此时乘以 $k$ 是剩余类上的一个置换，因而 $\{ka:a\in R\}$ 仍是完全剩余系，其中 $R$ 是任一完全剩余系。再加一个固定整数 $\ell$，映射 $x\mapsto kx+\ell$ 依然是置换

若模数是素数 $p$，欧几里得引理还给出

$$ab\equiv0\pmod p\quad\Longrightarrow\quad a\equiv0\pmod p\ \text{或}\ b\equiv0\pmod p$$

逆元与简化剩余系

当 $m>1$ 时，$a$ 模 $m$ 有乘法逆元的充要条件是 $\gcd(a,m)=1$。事实上，若扩展欧几里得算法给出

$$au+mv=1,$$

就有 $au\equiv1\pmod m$，所以 $u$ 是逆元。反过来，逆元的存在意味着 $1$ 是 $a,m$ 的整数线性组合，故二者互素。逆元作为剩余类是唯一的

例如 $3\cdot27=81\equiv1\pmod{40}$，所以 $3^{-1}\equiv27\pmod{40}$；而 $2$ 模 $40$ 没有逆元

把所有与 $m$ 互素的剩余类各取一个代表元，得到简化剩余系（RRS）。例如模 $10$ 的简化剩余系可以取 $\{1,3,7,9\}$。代表元本身不必是素数，“与模数互素”才是条件

简化剩余系的大小记为欧拉函数：

$$\phi(m)=\#\{1\le a\le m:\gcd(a,m)=1\}$$

约定 $\phi(1)=1$。模 $m$ 的这些可逆类在乘法下构成一个大小为 $\phi(m)$ 的群。若 $\gcd(k,m)=1$，乘以 $k$ 也会置换简化剩余系：每个乘积仍与 $m$ 互素，而约消保证它们互不相同

欧拉定理

设 $a_1,\ldots,a_{\phi(m)}$ 是简化剩余系，且 $\gcd(k,m)=1$。置换前后的所有元素相乘，有

$$(ka_1)\cdots(ka_{\phi(m)}) \equiv a_1\cdots a_{\phi(m)}\pmod m$$

右侧的乘积可逆，约去后得到欧拉定理：

$$\boxed{k^{\phi(m)}\equiv1\pmod m\qquad(\gcd(k,m)=1)}$$

当 $m=p$ 为素数，$\phi(p)=p-1$，这就是费马小定理 $p\nmid k\Rightarrow k^{p-1}\equiv1\pmod p$。例如 $3^{100}\equiv3^4\equiv4\pmod7$，因为 $100=16\cdot6+4$

指数能按某个周期缩减，需要底数可逆，并明确相应周期；不能仅由“两个指数模 $m$ 同余”推出幂同余

不同模数之间的关系

若 $m\mid M$，模 $M$ 同余蕴含模 $m$ 同余。写 $M=dm$，则一个模 $m$ 的类恰好分成 $d$ 个模 $M$ 的类：

$$[r]_m=\bigsqcup_{j=0}^{d-1}[r+jm]_M$$

例如 $[2]_5$ 在模 $25$ 下分成由 $2,7,12,17,22$ 代表的五个类。反过来，若 $a\equiv b$ 同时对若干模数 $m_i$ 成立，则

$$a\equiv b\pmod{\operatorname{lcm}(m_1,\ldots,m_s)}$$

这是因为每个 $m_i$ 都整除 $a-b$，故它们的最小公倍数也整除 $a-b$

拼装剩余系

若 $\gcd(m,n)=1$，分别令 $a$、$b$ 遍历模 $m$、模 $n$ 的完全剩余系，则

$$x=an+bm$$

遍历模 $mn$ 的一个完全剩余系。若 $a,b$ 分别只遍历简化剩余系，得到的正好是模 $mn$ 的简化剩余系。原因是模 $m$ 下 $x\equiv an$，模 $n$ 下 $x\equiv bm$；$n,m$ 在对应模数下均可逆，因此两项坐标都能由 $x$ 唯一找回。注意这里的 $a,b$ 是用来遍历剩余类的坐标；若要让 $x$ 匹配事先指定的两个余数，还需要给权重乘上逆元，下一篇的中国剩余定理会处理

另一种拼装是混合进制。令 $a$ 遍历模 $m$ 的完全剩余系、$b$ 遍历模 $n$ 的完全剩余系，则

$$x=a+mb$$

也遍历模 $mn$ 的完全剩余系，不要求 $m,n$ 互素。先对 $m$ 取余确定 $a$，再减去 $a$ 并除以 $m$，即可确定 $b$ 的类。连续应用便得到 $a_1+m_1a_2+m_1m_2a_3+\cdots$。这是一种逐位选代表元的方法；它一般不把各位的乘法变成独立的模乘法

欧拉函数的计算

互素模数的简化剩余系可以独立拼装，所以

$$\gcd(m,n)=1\quad\Longrightarrow\quad\phi(mn)=\phi(m)\phi(n)$$

对素数幂 $p^e$，$1$ 到 $p^e$ 中恰有 $p^{e-1}$ 个 $p$ 的倍数，因此

$$\phi(p^e)=p^e-p^{e-1}=p^{e-1}(p-1)$$

将 $n=\prod_{i=1}^s p_i^{e_i}$ 分解为互素的素数幂，得到

$$\boxed{\phi(n)=\prod_{i=1}^s p_i^{e_i-1}(p_i-1) =n\prod_{p\mid n}\left(1-\frac1p\right)}$$

例如 $10!=2^8\cdot3^4\cdot5^2\cdot7$，所以

$$\phi(10!)=128\cdot54\cdot20\cdot6=829440$$

乘法公式只适用于互素的两个输入。例如 $\phi(4)\phi(6)=4$，但 $\phi(24)=8$；应先把 $24$ 写成互素的 $2^3\cdot3$

最后还有一个有用的计数恒等式：

$$\boxed{\sum_{d\mid n}\phi(d)=n}$$

证明是按 $\gcd(a,n)$ 给 $1,\ldots,n$ 分组。若 $\gcd(a,n)=d$，则 $a/d$ 与 $n/d$ 互素，这一组恰有 $\phi(n/d)$ 个元素。对所有 $d\mid n$ 求和，再用 $d\leftrightarrow n/d$ 重新编号，就得到上式