3 中国剩余定理

第三阶段：CRT + 费马/欧拉定理 + 快速幂（详细版）

Confidence: 0.95

这一阶段是模运算从「会算」到「能打竞赛、懂密码学」的分水岭。我按你要求讲详细——每个定理都给：是什么 → 为什么成立（证明思路）→ 怎么用 → 完整例子 → 常见陷阱。内容较多，我分成三大块循序讲：

① 快速幂 (Fast Exponentiation) → ② 费马小定理 & 欧拉定理 (Fermat / Euler) → ③ 中国剩余定理 (CRT)

我特意把快速幂放最前面，因为它是后两块的计算引擎——费马、欧拉、RSA 全靠它。

---

第一块：快速幂 (Fast Exponentiation / Binary Exponentiation)

1.1 它解决什么问题

计算 $a^b\mathrm{mod}n$，其中 b 可能是天文数字（比如 $b=10^{18}$）。

朴素做法：连乘 b 次，$O(b)$。当 $b=10^{18}$ 时，宇宙毁灭都算不完。 快速幂：$O(\log b)$。$10^{18}$ 只需约 60 步。

这个加速是指数级 → 对数级，是密码学能实际运行的根本原因。

1.2 核心思想：二进制拆分 (Binary Decomposition)

任何指数 b 都能写成二进制。例如 $13=1101_2=8+4+1$，于是：

$a^{13}=a^{8+4+1}=a^8\cdot a^4\cdot a^1$

而 $a^1,a^2,a^4,a^8,\dots$ 这些「平方幂」可以反复平方得到，每次 $O(1)$：

$a^1\stackrel{\text{平方}}{\to }{a}^2\stackrel{\text{平方}}{\to }{a}^4\stackrel{\text{平方}}{\to }{a}^8$

算法：扫描 b 的二进制位，遇到 1 就把当前平方幂乘进答案。

1.3 完整手算示例：$3^{13}\mathrm{mod}7$

把 $13=1101_2$，从低位到高位扫描。维护两个量：result（答案，初始 1）和 base（当前平方幂，初始 3）。

步	b 当前位	base	是否乘入 result	result
初始	—	$3$	—	$1$
bit 0 = 1	取	$3$	是 → $1\times 3$	$3$
bit 1 = 0	—	$3^2=9\equiv 2$	否	$3$
bit 2 = 1	取	$2^2=4$	是 → $3\times 4=12\equiv 5$	$5$
bit 3 = 1	取	$4^2=16\equiv 2$	是 → $5\times 2=10\equiv 3$	$3$

$3^{13}\equiv 3(\mathrm{mod}7)$。

验证（用费马小定理偷看一眼，后面会讲）：$3^6\equiv 1(\mathrm{mod}7)$，所以 $3^{13}=3^{12}\cdot 3=(3^6{)}^2\cdot 3\equiv 1\cdot 3=3$ ✓

关键点：每一步 base 都立刻取模（$9\equiv 2$、$16\equiv 2$），数字永远不会爆炸。这就是为什么能算超大指数。

1.4 代码

# 手写快速幂（理解原理用）
def fast_pow(a, b, n):
    result = 1
    a %= n
    while b > 0:
        if b & 1:           # 当前二进制位是 1
            result = result * a % n
        a = a * a % n       # base 反复平方
        b >>= 1             # b 右移一位
    return result
 
print(fast_pow(3, 13, 7))   # 3
print(fast_pow(2, 100, 1000000007))  # 大指数也瞬间出结果
 
# Python 内置 pow 就是快速幂，实战直接用：
print(pow(3, 13, 7))        # 3

库安装方式（本块仅用内置函数，无需安装；做大规模数论实验可用 sympy）：

pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

---

第二块：费马小定理 & 欧拉定理 (Fermat’s Little Theorem & Euler’s Theorem)

这两个定理是「指数能取模」的理论基础，也是 RSA 的数学心脏。

2.1 费马小定理 (Fermat’s Little Theorem)

定理内容

设 p 是质数 (prime)，且 $\gcd (a,p)=1$（即 a 不是 p 的倍数），则：

$a^{p-1}\equiv 1(\mathrm{mod}p)$

等价的、更好记的形式（对任意 a 都成立，不要求互质）：

$a^p\equiv a(\mathrm{mod}p)$

为什么成立（证明思路）

考虑集合 $1,2,\dots ,p-1$，把每个元素乘以 a 再取模 p：

$a\cdot 1,a\cdot 2,\dots ,a\cdot (p-1)(\mathrm{mod}p)$

关键观察：因为 $\gcd (a,p)=1$，这个新集合恰好是原集合的重新排列 (permutation)——一一对应，不重不漏（这一步用到逆元的存在性）。

既然两个集合元素相同（只是顺序不同），它们的乘积相等：

$\underset{=a^{p-1}\cdot (p-1)!}{\underbrace{a\cdot 1\cdot a\cdot 2\cdots a\cdot (p-1)}}\equiv \underset{=(p-1)!}{\underbrace{1\cdot 2\cdots (p-1)}}(\mathrm{mod}p)$

两边约掉 $(p-1)!$（它与 p 互质，有逆元，可约），得：

$a^{p-1}\equiv 1(\mathrm{mod}p)■$

这个证明很美——核心就是「乘 a 是一个置换」。记住这个思路，欧拉定理是同一套。

用途一：求逆元（你已经会了）

$a^{-1}\equiv a^{p-2}(\mathrm{mod}p)$

因为 $a\cdot a^{p-2}=a^{p-1}\equiv 1$。配合快速幂，$O(\log p)$ 求逆元。

用途二：给指数「降幂」★重点

这是费马最强的应用：当模数是质数时，指数可以模 $(p-1)$。

$a^b\equiv a^{,b\mathrm{mod}(p-1)}(\mathrm{mod}p)(\gcd (a,p)=1)$

例子：求 $3^{100}\mathrm{mod}7$。

• 直接算 $3^{100}$ 是噩梦。
• 用费马：指数 $100\mathrm{mod}(7-1)=100\mathrm{mod}6=4$。
• 所以 $3^{100}\equiv 3^4=81\equiv 4(\mathrm{mod}7)$。

⚠️ 陷阱：降幂的模数是 $p-1$，不是 p！新手最常把这两个搞混。指数模 $p-1$，底数运算模 $p$。

2.2 欧拉定理 (Euler’s Theorem)

定理内容

费马小定理只对质数模成立。欧拉把它推广到任意模数 n：

设 $\gcd (a,n)=1$，则：

$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$

其中 $\phi (n)$ 是欧拉函数 (Euler’s totient function)——小于 n 且与 n 互质的正整数个数（也就是简化剩余系的大小，第一阶段讲过）。

退化关系：当 $n=p$ 为质数时，$\phi (p)=p-1$，欧拉定理就变回费马小定理。所以费马是欧拉的特例。

欧拉函数 $\phi (n)$ 怎么算 ★必会

公式：设 n 的质因数分解 (prime factorization) 为 $n=p_1^{k_1}{p}_2^{k_2}\cdots p_m^{k_m}$，则

$\phi (n)=n{\prod }_{i=1}^m\left(1-\frac{1}{p_i}\right)$

三个常用结论（记住能秒算很多情况）：

1. p 是质数：$\phi (p)=p-1$
2. 质数的幂：$\phi (p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$
3. 积性 (multiplicative)：若 $\gcd (m,n)=1$，则 $\phi (mn)=\phi (m)\phi (n)$

计算示例

例 1：$\phi (12)$。 $12=2^2\times 3$，用公式： $\phi (12)=12\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)=12\times \frac{1}{2}\times \frac{2}{3}=4$ 验证：与 12 互质的是 $1,5,7,11$，正好 4 个。✓

例 2：$\phi (100)$。 $100=2^2\times 5^2$： $\phi (100)=100\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)=100\times \frac{1}{2}\times \frac{4}{5}=40$

例 3（用积性）：$\phi (35)=\phi (5)\phi (7)=4\times 6=24$（因为 $\gcd (5,7)=1$）。

欧拉定理的用途：合数模的降幂

当模数 n 不是质数时，费马失效，改用欧拉：

$a^b\equiv a^{,b\mathrm{mod}\phi (n)}(\mathrm{mod}n)(\gcd (a,n)=1)$

例子：求 $7^{222}\mathrm{mod}10$。

• $\phi (10)=\phi (2)\phi (5)=1\times 4=4$
• 指数 $222\mathrm{mod}4=2$
• $7^{222}\equiv 7^2=49\equiv 9(\mathrm{mod}10)$

⚠️ 重要前提：欧拉降幂要求 $\gcd (a,n)=1$。如果不互质，需要用扩展欧拉定理 (Extended Euler)，那是更高阶的内容，竞赛偶尔考，现在先知道有这个边界即可。

2.3 费马 vs 欧拉 对照表

	费马小定理	欧拉定理
模数要求	必须质数 p	任意 n
核心式	$a^{p-1}\equiv 1$	$a^{\phi (n)}\equiv 1$
降幂模	$p-1$	$\phi (n)$
前提	$\gcd (a,p)=1$	$\gcd (a,n)=1$
关系	是欧拉的特例	是费马的推广

from sympy import totient   # 欧拉函数
 
# 欧拉函数
print(totient(12))    # 4
print(totient(100))   # 40
 
# 费马降幂：3^100 mod 7
print(pow(3, 100 % 6, 7))    # 4
 
# 欧拉降幂：7^222 mod 10
phi = int(totient(10))       # 4
print(pow(7, 222 % phi, 10)) # 9
 
# 费马求逆元：6^(-1) mod 13
print(pow(6, 13 - 2, 13))    # 11

库安装方式（用到 sympy 的 totient）：

pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

---

第三块：中国剩余定理 (CRT, Chinese Remainder Theorem) ★本阶段核心

3.1 它解决什么问题

求解一组同时成立的同余方程：

$\{\begin{array}{l}x\equiv a_1(\mathrm{mod}{n}_1)x\equiv a_2(\mathrm{mod}{n}_2)⋮x\equiv a_k(\mathrm{mod}{n}_k)\end{array}$

经典故事（《孙子算经》“物不知数”）：一堆东西，3 个一数余 2，5 个一数余 3，7 个一数余 2，问共几个？翻译成：

$x\equiv 2(\mathrm{mod}3),x\equiv 3(\mathrm{mod}5),x\equiv 2(\mathrm{mod}7)$

3.2 定理内容（模数两两互质的标准情形）

条件：模数 $n_1,n_2,\dots ,n_k$ 两两互质 (pairwise coprime)。

结论：存在唯一解，模 $N=n_1{n}_2\cdots n_k$。即在 $[0,N)$ 范围内恰好有一个 x 满足所有方程。

3.3 构造解的方法（详细步骤）★

设 $N=n_1{n}_2\cdots n_k$。对每个 i：

第 1 步：算 $N_i=N/n_i$（去掉第 i 个模数的乘积）。

第 2 步：算 $M_i=N_i^{-1}\mathrm{mod}{n}_i$（$N_i$ 在模 $n_i$ 下的逆元——用扩展欧几里得求）。

第 3 步：解就是把每一项加起来：

$x\equiv {\sum }_{i=1}^k{a}_i\cdot N_i\cdot M_i(\mathrm{mod}N)$

为什么这个构造对？（直觉）

看第 j 个方程要求 $x\equiv a_j(\mathrm{mod}{n}_j)$。在求和式里：

• 第 j 项 $a_j{N}_j{M}_j$：因为 $N_j{M}_j\equiv 1(\mathrm{mod}{n}_j)$，这项 $\equiv a_j(\mathrm{mod}{n}_j)$ ✓
• 其他项 $a_i{N}_i{M}_i(i\ne j)$：因为 $N_i$ 含因子 $n_j$，所以 $N_i\equiv 0(\mathrm{mod}{n}_j)$，整项消失 ✓

于是模 $n_j$ 时只剩 $a_j$，每个方程都满足。这个”每项只在自己的模数下存活、在别处归零”的设计是 CRT 的灵魂。

3.4 完整手算示例（解孙子问题）

解 $x\equiv 2(\mathrm{mod}3),x\equiv 3(\mathrm{mod}5),x\equiv 2(\mathrm{mod}7)$。

准备：$N=3\times 5\times 7=105$。

i	$n_i$	$a_i$	$N_i=N/n_i$	$M_i=N_i^{-1}\mathrm{mod}{n}_i$	$a_i{N}_i{M}_i$
1	3	2	$35$	$35\equiv 2$, $2^{-1}\equiv 2(\mathrm{mod}3)$	$2\times 35\times 2=140$
2	5	3	$21$	$21\equiv 1$, $1^{-1}\equiv 1(\mathrm{mod}5)$	$3\times 21\times 1=63$
3	7	2	$15$	$15\equiv 1$, $1^{-1}\equiv 1(\mathrm{mod}7)$	$2\times 15\times 1=30$

求和：$x\equiv 140+63+30=233(\mathrm{mod}105)$。 $233\mathrm{mod}105=233-2\times 105=23$。

答案：$x\equiv 23(\mathrm{mod}105)$。

验证：$23=7\times 3+2\Rightarrow 23\equiv 2(\mathrm{mod}3)$✓；$23=4\times 5+3\equiv 3(\mathrm{mod}5)$✓；$23=3\times 7+2\equiv 2(\mathrm{mod}7)$✓。三个全中！

3.5 模数不互质的情形（一般 CRT）

如果两个模数不互质，标准 CRT 失效，要用合并法 (merging)：

合并 $x\equiv a_1(\mathrm{mod}{n}_1)$ 和 $x\equiv a_2(\mathrm{mod}{n}_2)$：

• 设 $d=\gcd (n_1,n_2)$
• 有解的充要条件：$d\mid (a_1-a_2)$（否则无解）
• 有解时，合并成一个模 $\mathrm{lcm}(n_1,n_2)$ 的方程

这是竞赛进阶内容，原理是「两个方程联立用扩展欧几里得求 x」。现在你只需记住：不互质时先查 $d\mid (a_1-a_2)$，过了才有解。

3.6 CRT 代码

from math import gcd
 
def extgcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = extgcd(b, a % b)
    return g, y, x - (a // b) * y
 
def modinv(a, n):
    g, x, _ = extgcd(a, n)
    return x % n if g == 1 else None
 
# 标准 CRT（模数两两互质）
def crt(remainders, moduli):
    N = 1
    for m in moduli:
        N *= m
    x = 0
    for a_i, n_i in zip(remainders, moduli):
        N_i = N // n_i
        M_i = modinv(N_i, n_i)
        x += a_i * N_i * M_i
    return x % N
 
# 孙子问题
print(crt([2, 3, 2], [3, 5, 7]))   # 23
 
# Python 也可直接用 sympy
from sympy.ntheory.modular import crt as sympy_crt
print(sympy_crt([3, 5, 7], [2, 3, 2])[0])  # 23

库安装方式（用到 sympy 的 crt）：

pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

---

第三阶段全景速查表 (Master Cheat Sheet)

工具	核心式	前提	主要用途
快速幂 (fast exponentiation)	二进制拆分指数	无	算 $a^b\mathrm{mod}n$，$O(\log b)$
费马小定理 (Fermat)	$a^{p-1}\equiv 1$	p 质数, $\gcd (a,p)=1$	求逆元、指数模 $p-1$ 降幂
欧拉定理 (Euler)	$a^{\phi (n)}\equiv 1$	$\gcd (a,n)=1$	合数模降幂
欧拉函数 (totient)	$n\prod (1-1/p_i)$	—	算 $\phi (n)$
中国剩余定理 (CRT)	$x\equiv \sum a_i{N}_i{M}_i$	模数两两互质	解同余方程组

---

我的观点：第三阶段三块东西看似独立，其实是一条紧密的因果链，理解这条链比记住每个公式重要得多。快速幂是「手」——负责实际计算；费马/欧拉是「眼」——告诉你指数可以缩到多小（降幂），让快速幂有的放矢；CRT 是「分而治之的智慧」——把一个大模数问题拆成几个小模数问题分别解决，再拼回去。

这条链直接通向你的密码学兴趣：RSA 的解密本质就是这三者的合奏——用欧拉定理保证 $m^{ed}\equiv m$、用快速幂实际算出幂、用 CRT 把解密速度提升约 4 倍（CRT 优化是真实 RSA 实现里的标准技巧）。所以你现在学的不是孤立知识点，而是在拼装一台密码机器的核心齿轮。

我特别建议你把 CRT 的「每项只在自己模数下存活」这个设计彻底想透（3.3 那段直觉）。一旦你理解了「$N_i$ 在别的模数下归零、只在自己模数下靠 $M_i$ 变成 1」这个精巧的正交构造，你不仅会用 CRT，还会在后面碰到拉格朗日插值 (Lagrange interpolation)、傅里叶变换 (Fourier transform) 时产生强烈的既视感——它们用的是同一种「构造一组只在特定点非零的基」的思想。这是数学里反复出现的深层模式，CRT 是你第一次正面遇见它。

关键提醒 (Caveats)：

• 费马降幂的指数模 $p-1$，欧拉降幂模 $\phi (n)$，别和底数的模数 p / n 搞混——这是最高频错误
• 费马只对质数模有效；合数模一律用欧拉（且要 $\gcd (a,n)=1$）
• 标准 CRT 要求模数两两互质；不互质时先验 $d\mid (a_1-a_2)$ 再合并
• 降幂定理都要求 $\gcd (a,\text{模数})=1$；不互质时需扩展欧拉定理（更高阶）

下一步两个方向，你挑：① 出一套第三阶段练习题（CRT + 费马/欧拉降幂 + 快速幂三类，做成英文 PDF 试卷 + 单独答案册，延续上次格式）；② 直接进第四阶段：阶与原根 (order & primitive roots) + 二次剩余 (quadratic residues) + 离散对数 (discrete logarithm)。要哪个？

你说得对——P7（非互质 CRT）我在第三阶段正文里只是一笔带过（3.5 节只给了”先验 $d\mid (a_1-a_2)$“这一句），没有像其他知识点那样详细教你完整的合并步骤就直接出成题了。这是我的疏忽，抱歉。我现在把它补讲透。

---

补课：非互质模数的 CRT 合并 (CRT with Non-Coprime Moduli)

Confidence: 0.95

为什么标准 CRT 在这里失效

标准 CRT（第三阶段 3.2-3.4 讲的）有个硬性前提：模数两两互质 (pairwise coprime)。它构造解时要算 $N_i^{-1}\mathrm{mod}{n}_i$，而逆元只在互质时存在。一旦模数有公因子，这套构造直接崩掉，必须换方法。

两件事：先判存在，再做合并

非互质情形要分两步走。

第一步：一致性测试 (Consistency Test) —— 判断有没有解

合并两个方程 $x\equiv a_1(\mathrm{mod}{n}_1)$ 和 $x\equiv a_2(\mathrm{mod}{n}_2)$：

$\text{有解}⟺\gcd (n_1,n_2)\mid (a_1-a_2)$

为什么是这个条件？ 设 $d=\gcd (n_1,n_2)$。两个方程都”看得见”模 d 的部分：

• 第一个要求 $x\equiv a_1(\mathrm{mod}{n}_1)$，因为 $d\mid n_1$，所以也要求 $x\equiv a_1(\mathrm{mod}d)$
• 第二个同理要求 $x\equiv a_2(\mathrm{mod}d)$

两者要兼容，必须 $a_1\equiv a_2(\mathrm{mod}d)$，也就是 $d\mid (a_1-a_2)$。两个方程在”重叠的那部分模数”上不能打架。

第二步：合并 (Merge) —— 解存在时合成一个方程

测试通过后，两个方程可以合并成一个模 $\mathrm{lcm}(n_1,n_2)$ 的新方程。最实用的手算方法是代入法 (substitution)：

1. 把第一个方程写成参数形式：$x=a_1+n_{1}t$（t 是任意整数）
2. 代入第二个方程：$a_1+n_{1}t\equiv a_2(\mathrm{mod}{n}_2)$
3. 整理成关于 t 的线性同余：$n_{1}t\equiv (a_2-a_1)(\mathrm{mod}{n}_2)$
4. 这就回到了第二阶段的线性同余方程！ 解出 t（会有 $d$ 个解，取最小的 $t_0$）
5. 回代：$x=a_1+n_1{t}_0$，最终 $x\equiv a_1+n_1{t}_0(\mathrm{mod}\mathrm{lcm}(n_1,n_2))$

关键洞察：非互质 CRT 不是新东西——它把问题转化成了你已经会的线性同余方程（第二阶段）。这就是为什么我说数论是层层搭建的。

---

完整手算示例（就用 P7 的题）

解 $x\equiv 5(\mathrm{mod}6),x\equiv 11(\mathrm{mod}15)$。

第一步：一致性测试 $d=\gcd (6,15)=3,a_1-a_2=5-11=-6,3\mid (-6)✓$ 有解。解将唯一存在于模 $\mathrm{lcm}(6,15)=30$。

第二步：代入法合并

① 写参数形式：$x=5+6t$

② 代入第二个方程： $5+6t\equiv 11(\mathrm{mod}15)$

③ 整理： $6t\equiv 6(\mathrm{mod}15)$

④ 解这个线性同余（第二阶段技能）：$\gcd (6,15)=3$，$3\mid 6$ ✓，有 3 个解。整体除以 3： $2t\equiv 2(\mathrm{mod}5);\Rightarrow ;t\equiv 1(\mathrm{mod}5)$ 取最小 $t_0=1$。

⑤ 回代： $x=5+6\times 1=11$

答案：$x\equiv 11(\mathrm{mod}30)$。

验证：$11=1\times 6+5\equiv 5(\mathrm{mod}6)$ ✓；$11\equiv 11(\mathrm{mod}15)$ ✓。两个都满足！

---

无解的反例（看清陷阱长什么样）

解 $x\equiv 1(\mathrm{mod}6),x\equiv 2(\mathrm{mod}15)$。

一致性测试：$d=\gcd (6,15)=3$，$a_1-a_2=1-2=-1$，但 $3\nmid (-1)$ ✗

无解。直觉：第一个方程要求 $x\equiv 1(\mathrm{mod}3)$（因为 $3\mid 6$），第二个要求 $x\equiv 2(\mathrm{mod}3)$（因为 $3\mid 15$）。同一个 x 不可能模 3 既余 1 又余 2，自相矛盾。

这就是为什么必须先做测试再合并——不测就埋头算，会在矛盾里绕圈子。

---

多个非互质方程怎么办

如果有三个以上方程，两两滚动合并：先合并前两个得一个新方程，再用结果和第三个合并，依此类推。每次合并都先做一致性测试。这叫迭代合并 (iterative merging)。

---

Python 实现

from math import gcd
 
def merge(a1, n1, a2, n2):
    """合并 x≡a1(mod n1) 和 x≡a2(mod n2)，返回 (a, n) 即 x≡a(mod n)；无解返回 None"""
    d = gcd(n1, n2)
    if (a2 - a1) % d != 0:
        return None                      # 一致性测试失败，无解
    lcm = n1 // d * n2
    # 解 n1 * t ≡ (a2-a1) (mod n2)
    t = ((a2 - a1) // d * pow(n1 // d, -1, n2 // d)) % (n2 // d)
    a = (a1 + n1 * t) % lcm
    return a, lcm
 
# P7
print(merge(5, 6, 11, 15))    # (11, 30)
# 无解反例
print(merge(1, 6, 2, 15))     # None
 
# 通用 sympy（自动处理互质/非互质）
from sympy.ntheory.modular import crt
print(crt([6, 15], [5, 11]))  # (11, 30)
print(crt([6, 15], [1, 2]))   # None

库安装方式（用到 sympy）：

pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

---

我的观点：抱歉这个知识点我之前教得太草率了——出题前应该先教完整。不过现在补反而有个好处：你已经做过 P1-P6，对 CRT 的”互质标准情形”很熟了，这时候再看”非互质”，你能清楚地看到两者的分界线在哪——互质时用 $N_i{M}_i$ 的正交构造（优雅但要求严格），非互质时退回代入法转成线性同余（朴素但通用）。理解了这个分界，你对 CRT 的认识就完整了：它不是一个公式，而是一个根据模数关系选择策略的框架。

我也想强调：非互质 CRT 把问题化归 (reduce) 成线性同余方程，这种”把新问题翻译成已解决的旧问题”的思路，是整个数学和算法设计的核心方法论。你在 CMU 的算法课（比如 15-451）会反复见到”归约”这个词——CRT 合并就是一个干净的归约实例。

关键提醒 (Caveats)：

• 非互质合并永远先做一致性测试 $d\mid (a_1-a_2)$，通过才能合并
• 合并后的模数是 $\mathrm{lcm}(n_1,n_2)$，不是 $n_1{n}_2$（互质时两者才相等）
• 代入法第④步解出的 t 有 $d$ 个，取最小的 $t_0$ 即可（不同 $t_0$ 回代得到的 x 模 lcm 是同一个）

现在 P7 的完整方法你有了。要不要现在重做一遍 P7（你应该能轻松拿下了），还是接着把整张卷子做完？做完把 P2、P4、P7 发我批改，或者直接说「进第四阶段」都行。

说的是这个结论：

对于 $n>1$，所有满足 $1\le k\le n$ 且 $\gcd (k,n)=1$ 的整数之和等于 $\frac{n\cdot \phi (n)}{2}$。

为什么成立（配对法 / pairing argument）：

核心是一个对称性观察：

如果 $\gcd (k,n)=1$，那么 $\gcd (n-k,n)=1$。

证明很简单：$\gcd (n-k,n)=\gcd (-k,n)=\gcd (k,n)=1$（因为 $\gcd$ 对模 $n$ 是不变的）。

这说明：与 $n$ 互质的数可以两两配对，每一对是 $(k,n-k)$，而且每对的和恰好是：

$k+(n-k)=n$

数一数有多少对：

与 $n$ 互质的数总共有 $\phi (n)$ 个，它们配成 $\frac{\phi (n)}{2}$ 对，每对和为 $n$，所以总和：

$S=\underset{\text{每对的和}}{\underbrace{n}}\times \underset{\text{对数}}{\underbrace{\frac{\phi (n)}{2}}}=\frac{n\cdot \phi (n)}{2}$

几个小细节：

• 当 $n>1$ 时，$\phi (n)$ 一定是偶数，所以能整除成整数对，不用担心配对落单。
• 唯一需要小心的是 $k=n-k$ 的情况，即 $k=n/2$。但 $n/2$ 与 $n$ 不互质（除非 $n\le 2$），所以这种”自己配自己”的情况不会出现在互质集合里，配对干净。
• $n=1$ 是特例（$k=1$ 自己和自己配，和为 1），但本题 $n=2025$ 用不上。

举个小例子验证，$n=6$，与 6 互质的数是 $1,5$，和为 $6$。公式：$\frac{6\cdot \phi (6)}{2}=\frac{6\cdot 2}{2}=6$ ✓。

再来 $n=10$，互质数 $1,3,7,9$，和为 $20$。公式：$\frac{10\cdot 4}{2}=20$ ✓。

Confidence: 0.99

这个结论在数论里很常用，本质就是欧拉函数（Euler’s totient function）的对称性，记住”配对凑 $n$“这个画面就不会忘。