第 14 章：补充证明：逆元、唯一分解与CRT

返回目录

这一章供遇到“这一步还没证明”时回查。第1—12章已经解释主线的定理与推导；这里补足它们背后的基础结论。可按小节标题选读，不需要一次全部读完。

14.1 从最小正线性组合证明裴蜀等式

定理。 对不全为零的整数 $a,b$ ，存在整数 $x,y$ ，使

$ax+by=\gcd(a,b).$

令

$S=\{ax+by:x,y\in\mathbb Z,\ ax+by>0\}.$

集合非空：若 $a\ne0$ ，选择 $x=1$ 或 $-1$ 、 $y=0$ 即得到 $|a|$ ；否则用 $|b|$ 。由良序原理， $S$ 有最小元素 $d>0$ ，写作 $d=ax_0+by_0$ 。

对 $a$ 作带余除法： $a=qd+r$ ， $0\le r<d$ 。于是

$r=a-qd=a(1-qx_0)+b(-qy_0).$

如果 $r>0$ ，它也是 $S$ 的元素，却比 $d$ 小，矛盾。故 $r=0$ ，即 $d\mid a$ 。同理 $d\mid b$ 。

另一方面，任意正公约数 $c$ 都整除 $a,b$ 的整数线性组合，所以 $c\mid d$ ，进而 $c\le d$ 。因此 $d$ 既是公约数，又不小于任何正公约数，正是 $\gcd(a,b)$ 。所需的 $x_0,y_0$ 已由构造给出。证毕。

关键不是猜出线性组合，而是先取最小正组合，再用带余除法排除更小的正组合。这个证明不依赖质因数分解，后面的论证因而没有循环。

14.2 互质消去律与欧几里得引理

若 $\gcd(a,n)=1$ 且 $n\mid ab$ ，由裴蜀等式取 $ax+ny=1$ ，乘以 $b$ ：

$b=abx+nby.$

右侧两项均被 $n$ 整除，故 $n\mid b$ 。这就是互质消去律，其中 $n$ 不必是质数。

作为特例，若 $p$ 是质数且 $p\mid ab$ ，则 $p\mid a$ 或 $p\mid b$ 。因为一旦 $p\nmid a$ ，质数的因数只有 $1,p$ ，所以 $\gcd(a,p)=1$ ，可应用消去律。这称为欧几里得引理。

质数条件不可随意删去： $6\mid2\cdot3$ ，但 $6$ 不整除任何一个因子。反复应用欧几里得引理，可得质数若整除有限乘积，必整除至少一个因子。

14.3 模逆元存在的充要条件

$a$ 模 $n$ 的逆元是满足 $au\equiv1\pmod n$ 的整数 $u$ 。对 $n\ge2$ ，有

$a\text{ 模 }n\text{ 有逆元}\quad\Longleftrightarrow\quad\gcd(a,n)=1.$

充分性：由 $ax+ny=1$ ，取 $u=x$ 。

必要性：若 $au-nv=1$ ， $a,n$ 的每个公约数都整除左边，因此整除 $1$ ，所以只能为 $1$ 。

逆元在模 $n$ 意义下唯一：若 $au\equiv av\equiv1$ ，则 $n\mid a(u-v)$ ；由互质消去律， $n\mid(u-v)$ 。

因此，当 $\gcd(a,n)=1$ 时，从 $ab\equiv ac\pmod n$ 可以乘以逆元，推出 $b\equiv c\pmod n$ 。这是后面约去阶乘或剩余类乘积的依据。

14.4 两个常用推论

互质因子的乘积仍与模数互质。 若 $ax+ny=1$ 、 $bu+nv=1$ ，相乘得到

$abxu+n(axv+buy+nyv)=1.$

任意 $ab,n$ 的公约数都整除 $1$ ，故 $\gcd(ab,n)=1$ 。有限多个因子可归纳处理。

互质的两个数都整除一个整数，则其乘积也整除。 若 $\gcd(m,n)=1$ 、 $m\mid A$ 、 $n\mid A$ ，写 $A=mt$ 。由 $n\mid mt$ 与消去律， $n\mid t$ ，故 $mn\mid A$ 。

14.5 如何实际计算逆元

带余除法给出 $\gcd(a,b)=\gcd(b,r)$ ，因为 $a=qb+r$ 使两对数的公约数完全相同。反复除法时非零余数严格变小，最终停在最大公约数；再回代即可找到裴蜀系数。这就是扩展欧几里得算法。

例如 $40=13\cdot3+1$ ，所以 $1=40-13\cdot3$ ，从而

$3^{-1}\equiv-13\equiv27\pmod{40}.$

这里逆元符号表示模运算中的整数剩余类，不是普通分数 $1/3$ 。

14.6 定理的准确表述

每个整数 $n>1$ 都能写成有限个质数的乘积。除排列顺序外，质因子及其重数唯一。将相同质因子合并，可以写成

$n=p_1^{\alpha_1}\cdots p_k^{\alpha_k},$

其中 $p_i$ 两两不同， $\alpha_i\ge1$ 。例如 $60=2^2\cdot3\cdot5$ 。

“存在”和“唯一”是两个不同问题，不能只证明能拆分，就认为不可能有另一种拆分。

14.7 存在性：强归纳法

$n=2$ 自身是质数。假设所有满足 $2\le m<n$ 的整数均可分解。

若 $n$ 是质数，结论立即成立。若 $n$ 是合数，可写 $n=ab$ ，其中 $1<a,b<n$ 。由归纳假设， $a,b$ 都是质数的有限乘积，合在一起给出 $n$ 的分解。因此对所有 $n>1$ 成立。

14.8 唯一性：配对和终止分别证明

假设

$p_1\cdots p_r=q_1\cdots q_s$

是两种分解。 $p_1$ 整除右侧，由欧几里得引理，它整除某个 $q_j$ 。两个数都是质数，所以 $p_1=q_j$ 。重排右边，将它放到第一位，再在普通整数等式中约去相同质数。

重复此步骤，每次都会找到并约去一对相同质因子。

为什么两边一定同时约完？ 假设 $r<s$ 。约去左侧全部 $r$ 个因子后，得到

$1=q_{r+1}\cdots q_s.$

右侧至少剩一个质数，每个质数都不小于 $2$ ，故乘积大于 $1$ ，矛盾。 $r>s$ 同样矛盾。所以 $r=s$ ，每一步配对后所有质因子一一相等，重数也相同。证毕。

能够配对来自欧几里得引理；必然同时结束来自非空质数乘积大于 $1$ 。这是原对话“为什么最终同时约完”的完整回答。

14.9 最大公约数与最小公倍数的质数幂描述

给定有限多个正整数，把出现的质数统一记为 $p_j$ ，缺少某个质因子时指数记为 $0$ 。两个数的最大公约数取每个指数的最小值，最小公倍数取最大值：

$\gcd(m,n)=\prod_jp_j^{\min(\alpha_j,\beta_j)},\qquad \operatorname{lcm}(m,n)=\prod_jp_j^{\max(\alpha_j,\beta_j)}.$

理由是：由唯一分解，一个正整数整除另一个，当且仅当每个质数指数都不超过对方。公约数和公倍数的条件遂逐个指数决定。

于是 $\gcd(m,n)\operatorname{lcm}(m,n)=mn$ 。一个整数同时被所有 $m_i$ 整除，当且仅当被 $\operatorname{lcm}(m_1,\ldots,m_k)$ 整除；整数为 $0$ 的情况也显然成立。这将说明中国剩余定理的解周期。

14.10 一般容斥为何成立

令 $A_i$ 是能被 $p_i$ 整除的整数集合。统计其补集时，按所选集合个数交替加减，并把空交集解释为全部 $n$ 个整数。

对一个落入恰好 $j$ 个 $A_i$ 的整数，它在展开中的总权重为

$\sum_{t=0}^{j}(-1)^t\binom jt=(1-1)^j.$

若 $j=0$ ，权重为 $1$ ；若 $j\ge1$ ，权重为 $0$ 。所以恰好只计入互质整数，每个计入一次。这证明了容斥，而非仅把它作为未证明的工具使用。

记 $I=\{1,\ldots,k\}$ 。不同质数互质，每个交集对应其乘积的倍数，故

$\varphi(n)=n\sum_{J\subseteq I}(-1)^{|J|}\prod_{i\in J}\frac1{p_i}.$

空乘积取 $1$ 。展开 $\prod_i(1-1/p_i)$ 时，从每个括号选 $1$ 或 $-1/p_i$ 。选择负项的下标恰好形成子集 $J$ ，贡献 $(-1)^{|J|}\prod_{i\in J}1/p_i$ ；每个子集出现一次。因此

$\boxed{\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)}.$

乘积公式是容斥展开的因式分解表达。 质因子指数虽影响 $n$ ，排除的倍数类别却只由不同质因子决定，所以每个质数只出现一个括号。

14.11 两两互质模数的定理

设正整数 $m_1,\ldots,m_k$ 两两互质，余数 $a_i$ 为任意整数，令 $M=m_1\cdots m_k$ 。则

$x\equiv a_i\pmod{m_i}\quad(i=1,\ldots,k)$

一定有解，所有解恰为 $x=x_0+tM$ ， $t\in\mathbb Z$ 。

“唯一”指模 $M$ 的唯一剩余类，而非只有一个整数解。模数为 $1$ 的条件不限制任何整数，可以删除；若全部为 $1$ ，全部整数就是模 $1$ 的一个剩余类。以下构造处理剩余的模数。

14.12 存在性：构造对自己的模数余一、对其他余零的项

令 $M_i=M/m_i$ 。因为其他每个 $m_j$ 都与 $m_i$ 互质，第 13.4 节的乘积互质性质给出 $\gcd(M_i,m_i)=1$ 。

由裴蜀等式，取 $M_iu_i+m_iv_i=1$ ，令 $E_i=M_iu_i$ 。于是

$E_i\equiv1\pmod{m_i},\qquad E_i\equiv0\pmod{m_j}\ (j\ne i).$

第二式来自 $m_j\mid M_i$ 。再取

$x_0=\sum_{i=1}^ka_iE_i=\sum_{i=1}^ka_iM_iu_i.$

对任意固定 $m_j$ 取模，其余项全为 $0$ ，只有 $a_jE_j\equiv a_j$ ，所以满足全部方程。存在性得证。

14.13 唯一性与全部解

若 $x,y$ 都是解，则每个 $m_i$ 都整除 $x-y$ 。由于模数两两互质，任意部分乘积仍与下一个模数互质，可反复用互质乘积整除推论，得 $M\mid(x-y)$ 。

反过来， $x_0+tM$ 对各模数都与 $x_0$ 同余，所以仍是解。因此全部解恰为该形式。

14.14 手算构造公式

求 $x\equiv2\pmod3$ 、 $x\equiv3\pmod5$ 、 $x\equiv2\pmod7$ 。

$M=105$ ， $M_1=35$ 、 $M_2=21$ 、 $M_3=15$ ；各自逆元可取 $2,1,1$ ，因为对应乘积模自身模数均为 $1$ 。于是

$x_0=2\cdot35\cdot2+3\cdot21+2\cdot15=233\equiv23\pmod{105}.$

全部解 $x=23+105t$ 。直接检验 $23$ 分别余 $2,3,2$ 。

14.15 相容性条件与正确周期

对任意正整数模数 $m_1,\ldots,m_k$ ，方程组 $x\equiv a_i\pmod{m_i}$ 有解，当且仅当

$\boxed{\gcd(m_i,m_j)\mid(a_i-a_j)\quad\text{对全部 }i,j}.$

若有解，令 $L=\operatorname{lcm}(m_1,\ldots,m_k)$ ，全部解恰为 $x=x_0+tL$ 。

模数不互质时，相容性有实际限制。例如 $x\equiv2\pmod6$ 与 $x\equiv4\pmod9$ 无解，因为公约数 $3$ 不整除余数差 $2$ 。互质时公约数为 $1$ ，条件自动满足，且 $L$ 等于乘积，所以标准形式是特殊情形。

14.16 两个模数：必要性

考虑 $x\equiv a\pmod m$ 、 $x\equiv b\pmod n$ ，记 $g=\gcd(m,n)$ 。

若存在 $x$ ， $g$ 整除 $x-a$ 与 $x-b$ ，也就整除两者之差 $b-a$ 。因此 $g\mid(b-a)$ 必要。

14.17 两个模数：充分性与构造

假设 $g\mid(b-a)$ ，写 $m=gm'$ 、 $n=gn'$ 、 $b-a=gc$ ，其中 $m',n'$ 互质。

先令 $x=a+mt$ ，保证第一个方程。第二个方程要求 $mt\equiv b-a\pmod n$ ，等价于存在整数 $s$ 使

$mt-ns=b-a\quad\Longleftrightarrow\quad m't-n's=c.$

用裴蜀等式取 $m'u+n'v=1$ ，令 $t=cu$ 、 $s=-cv$ ，便满足要求，因此可取 $x_0=a+mcu$ 。充分性得证。

若 $x,y$ 均为解，则 $m,n$ 都整除 $x-y$ ，由第 13.9 节， $\operatorname{lcm}(m,n)\mid(x-y)$ 。反过来加上该最小公倍数的任意整数倍仍是解，因而全部解及周期成立。

14.18 非互质的手算例子

求 $x\equiv2\pmod6$ 、 $x\equiv5\pmod9$ 。公约数 $3$ 整除余数差 $3$ ，所以有解。

写 $x=2+6t$ ，代入得到 $6t\equiv3\pmod9$ 。这一同余等价于 $2t\equiv1\pmod3$ ：是同时将整除等式的两边及模数除以 $3$ ，并非保持原模数的无条件约分。

所以 $t\equiv2\pmod3$ ，取 $t=2+3s$ ，得

$x=14+18s,\qquad x\equiv14\pmod{18}.$

周期是 $\operatorname{lcm}(6,9)=18$ ，不是乘积 $54$ 。

14.19 多个模数：为何两两相容足以给出共同解

必要性仍来自任意两个方程的差。充分性必须另证，不能只说“每一对有解，所以整体有解”。以下使用质数幂分解。

写

$L=\operatorname{lcm}(m_1,\ldots,m_k)=\prod_{j=1}^{r}p_j^{e_j}.$

每个 $e_j$ 是所有模数中该质数指数的最大值，所以可选一个下标 $h(j)$ ，使 $p_j^{e_j}\mid m_{h(j)}$ 。提取约束

$x\equiv a_{h(j)}\pmod{p_j^{e_j}}\quad(j=1,\ldots,r).$

这些模数是不同质数的幂，两两互质，由标准形式得到公共解 $x_0$ 。

现在证明它满足原方程。固定 $i$ ，设 $p_j$ 在 $m_i$ 中的指数为 $f_{ij}\le e_j$ 。若 $f_{ij}>0$ ，该质数幂同时整除 $m_i$ 与 $m_{h(j)}$ ，故

$p_j^{f_{ij}}\mid\gcd(m_i,m_{h(j)})\mid(a_i-a_{h(j)}).$

而构造保证 $x_0\equiv a_{h(j)}\pmod{p_j^{e_j}}$ ，所以降到 $p_j^{f_{ij}}$ 后仍成立，结合相容性得 $x_0\equiv a_i$ 模该质数幂。对 $m_i$ 的所有不同质数幂都成立，互质乘积整除推论给出 $m_i\mid(x_0-a_i)$ 。

由于 $i$ 任意，满足全部原方程。若 $L=1$ ，则全部模数为 $1$ ，直接取任意整数即可。

若选择最大指数的模数有多个，相容性使它们的余数模该质数幂相同，因此提取约束没有歧义。

14.20 唯一性与一个多模数例子

任意两个解之差被所有 $m_i$ 整除，因此被 $L$ 整除； $x_0+tL$ 又总是解。所以解模 $L$ 唯一。 $L$ 也是解集合的最小正平移周期：任何保持解的正平移量都必须被全部模数整除，因此被 $L$ 整除。

例如取 $m_1=12,m_2=18,m_3=20$ ，余数分别为 $5,11,17$ 。三个公约数为 $6,4,2$ ，都整除对应余数差。 $L=180=4\cdot9\cdot5$ ，可提取

$x\equiv1\pmod4,\quad x\equiv2\pmod9,\quad x\equiv2\pmod5.$

取 $x_0=137$ ，逐项检验模 $12,18,20$ 分别余 $5,11,17$ ，故全部解为 $137+180t$ 。

第 14 章：补充证明：逆元、唯一分解与CRT ​

14.1 从最小正线性组合证明裴蜀等式 ​

14.2 互质消去律与欧几里得引理 ​

14.3 模逆元存在的充要条件 ​

14.4 两个常用推论 ​

14.5 如何实际计算逆元 ​

14.6 定理的准确表述 ​

14.7 存在性：强归纳法 ​

14.8 唯一性：配对和终止分别证明 ​

14.9 最大公约数与最小公倍数的质数幂描述 ​

14.10 一般容斥为何成立 ​

14.11 两两互质模数的定理 ​

14.12 存在性：构造对自己的模数余一、对其他余零的项 ​

14.13 唯一性与全部解 ​

14.14 手算构造公式 ​

14.15 相容性条件与正确周期 ​

14.16 两个模数：必要性 ​

14.17 两个模数：充分性与构造 ​

14.18 非互质的手算例子 ​

14.19 多个模数：为何两两相容足以给出共同解 ​

14.20 唯一性与一个多模数例子 ​