横向补全：Stage 1–3 的全部缺口（详细版）

Confidence: 0.93

好，一次补完类别 A 的所有缺口。我按”原阶段归属”组织，每个知识点给：是什么 → 为什么 → 怎么用 → 例子 → 代码/陷阱。这一节信息密度高，但补完后你 Stage 1–3 就是真正的”无死角”了。

六个缺口：① Wilson 定理 → ② 环 $Z / n Z$ 视角 → ③ 多元线性同余 → ④ 批量逆元 → ⑤ 扩展欧拉定理 → ⑥ Lucas 定理 + 线性筛。

补 Stage 1

① 威尔逊定理 (Wilson’s Theorem)

内容

$p 是质数 ⟺ (p - 1)! \equiv - 1 (mod p)$

注意这是充要条件 (if and only if)——它既是质数的必要条件，也是充分条件，所以理论上能用来判素性。

为什么成立（证明思路）

考虑 $1, 2, \dots, p - 1$ ，每个元素在模 p 下都有唯一逆元（因为都与 p 互质）。把元素两两配对：每个 $a$ 和它的逆元 $a^{- 1}$ 配对，乘积是 1。

唯一的例外是自己是自己逆元的元素，即满足 $a^{2} \equiv 1 (mod p)$ 的 $a$ 。解这个方程： $a \equiv \pm 1$ ，也就是 $a = 1$ 和 $a = p - 1$ 。

所以 $(p - 1)!$ 里，除了 $1$ 和 $p - 1$ ，其余元素全部两两配对约成 1，剩下：

$(p - 1)! \equiv 1 \times (p - 1) \equiv - 1 (mod p) ■$

例子

$p = 7$ ： $(7 - 1)! = 720$ 。 $720 = 102 \times 7 + 6 \equiv 6 \equiv - 1 (mod 7)$ ✓

$p = 5$ ： $4! = 24 = 4 \times 5 + 4 \equiv 4 \equiv - 1 (mod 5)$ ✓

用途与陷阱

理论价值大于实用：判素性要算 $(p - 1)!$ ，比试除法还慢，实际不用它判素。
真正用途：证明题、以及推导某些特殊同余（如 $(\frac{p - 1}{2})!$ 的性质，和二次剩余相关，Stage 4 会用）。
⚠️ 反方向也成立：若 $n$ 合数且 $n > 4$ ，则 $(n - 1)! \equiv 0 (mod n)$ 。

② 环视角： $Z / n Z$ 与 $(Z / n Z)^{*}$

这不是新计算，而是给你一个代数语言，让你看清前面学的东西”住在什么结构里”。这是通往 Stage 4 群论的桥。

$Z / n Z$ 是一个环 (ring)

把模 n 的 n 个同余类 $[0], [1], \dots, [n - 1]$ 看成一个整体，它带着两种运算：

加法： $[a] + [b] = [a + b]$ —— 永远封闭，永远有逆（ $[a]$ 的加法逆是 $[n - a]$ ）
乘法： $[a] \times [b] = [ab]$ —— 封闭，但不一定有逆

满足”加法成群、乘法封闭且分配”的结构，数学上叫环 (ring)。 $Z / n Z$ 就是”模 n 整数环”。

$(Z / n Z)^{*}$ 是一个群 (group)

把环里有乘法逆元的元素（即与 n 互质的同余类）单独拎出来，组成集合 $(Z / n Z)^{*}$ ：

$(Z / n Z)^{*} = [a] : g cd (a, n) = 1$

这个集合在乘法下成群 (group)——封闭、有单位元 $[1]$ 、每个元素有逆、满足结合律。

它的大小恰好是 $φ (n)$ ！ 这就把欧拉函数的真正含义点破了： $φ (n)$ 不只是”互质元素的个数”，而是”乘法群的阶 (order of the group)“。

为什么这个视角重要

一旦你这样看，前面学的定理瞬间”显然化”：

你学过的	群论翻译
欧拉定理 $a^{φ (n)} \equiv 1$	“群里任何元素的 $∣ G ∣$ 次方 = 单位元”（拉格朗日定理的推论）
费马小定理	同上，群是 $(Z / p Z)^{*}$ ，阶 $p - 1$
模逆元存在 $⟺$ 互质	”元素属于群 $⟺$ 它在群里”（同义反复）

这是 Stage 4 的入口：当你能自然地把模运算看成”群里的运算”，原根（群的生成元）、离散对数（群里的”取对数”）就都是顺理成章的概念了。

例子

$n = 8$ ： $(Z /8 Z)^{*} = 1, 3, 5, 7$ ，大小 $φ (8) = 4$ 。验证封闭： $3 \times 5 = 15 \equiv 7$ 、 $3 \times 7 = 21 \equiv 5$ 、 $5 \times 7 = 35 \equiv 3$ ——乘来乘去永远落在这 4 个数里，确实是个群。

补 Stage 2

③ 多元线性同余 / 线性丢番图方程 (Multivariable Linear Congruence)

问题形式

$a x + b y \equiv c (mod n) 或等价地 a x + b y = c (整数解)$

求整数对 $(x, y)$ 。这叫线性丢番图方程 (linear Diophantine equation)。

有解条件与求法

有解 $⟺ g cd (a, b) ∣ c$ （和单变量同余的判据同源）。

三步求法：

用扩展欧几里得求 $g cd (a, b) = g$ 及一组 $a x_{0} + b y_{0} = g$
两边乘 $\frac{c}{g}$ ，得一个特解 (particular solution)： $x_{1} = x_{0} \cdot \frac{c}{g}, y_{1} = y_{0} \cdot \frac{c}{g}$
通解 (general solution) 加上齐次部分： $x = x_{1} + \frac{b}{g}, t, y = y_{1} - \frac{a}{g}, t, t \in Z$

完整例子

解 $6 x + 15 y = 12$ 。

$g cd (6, 15) = 3$ ，扩展欧几里得： $6 \times (- 2) + 15 \times 1 = 3$ ，即 $x_{0} = - 2, y_{0} = 1$
$3 ∣ 12$ ✓，乘 $\frac{12}{3} = 4$ ：特解 $x_{1} = - 8, y_{1} = 4$
通解： $x = - 8 + 5 t, y = 4 - 2 t$

验证（取 $t = 2$ ）： $x = 2, y = 0$ ， $6 \times 2 + 15 \times 0 = 12$ ✓；（取 $t = 1$ ） $x = - 3, y = 2$ ， $6 \times (- 3) + 15 \times 2 = - 18 + 30 = 12$ ✓

几何直觉

$6 x + 15 y = 12$ 是一条直线，整数解是这条线穿过的格点 (lattice points)。通解里的 $t$ 就是”沿直线一格一格跳”的步数，步长由 $\frac{b}{g}, \frac{a}{g}$ 决定。

④ 批量求逆元 (Batch Modular Inverse)

问题

求 $1, 2, \dots, n$ 模 p 的所有逆元。逐个用费马要 $O (n lo g p)$ ，有更快的 $O (n)$ 递推法——竞赛高频技巧。

递推公式（线性求逆）

对质数 p，设 $inv [i] = i^{- 1} mod p$ ，递推式：

$inv [i] = - ⌊ \frac{p}{i} ⌋ \cdot inv [p mod i] mod p$

边界 $inv [1] = 1$ 。

为什么成立（推导）

设 $p = ⌊ p / i ⌋ \cdot i + (p mod i)$ 。两边模 p：

$⌊ p / i ⌋ \cdot i + (p mod i) \equiv 0 (mod p)$

两边乘 $i^{- 1} \cdot (p mod i)^{- 1}$ ，整理就得到上面的递推式。精妙处：求 $inv [i]$ 用到的 $inv [p mod i]$ 下标更小，已经算过，所以一遍扫过去 $O (n)$ 。

例子（ $p = 7$ ，求 $1 \sim 6$ 的逆元）

$inv [1] inv [2] inv [3] inv [4] inv [5] inv [6] = 1 = - ⌊ 7/2 ⌋ \cdot inv [7 mod 2] = - 3 \cdot inv [1] = - 3 \equiv 4 = - ⌊ 7/3 ⌋ \cdot inv [1] = - 2 \cdot 1 = - 2 \equiv 5 = - ⌊ 7/4 ⌋ \cdot inv [3] = - 1 \cdot 5 = - 5 \equiv 2 = - ⌊ 7/5 ⌋ \cdot inv [2] = - 1 \cdot 4 = - 4 \equiv 3 = - ⌊ 7/6 ⌋ \cdot inv [1] = - 1 \cdot 1 = - 1 \equiv 6$

验证： $2 \times 4 = 8 \equiv 1$ ✓， $3 \times 5 = 15 \equiv 1$ ✓， $4 \times 2 = 8 \equiv 1$ ✓，全对。

补 Stage 3

⑤ 扩展欧拉定理 (Extended Euler’s Theorem) ★最重要的补充

解决什么

欧拉定理降幂要求 $g cd (a, n) = 1$ 。当 a 和 n 不互质时（普通欧拉失效），用扩展欧拉。它还能处理超大指数甚至幂塔 (power tower) $a^{a^{a^{\dots}}}$ 。

定理内容（三种情况）

求 $a^{b} mod n$ ：

$a^{b} \equiv {a^{b} a^{, (b mod φ (n)) + φ (n)} if b < φ (n) if b \geq φ (n) (mod n)$

核心区别：普通欧拉是 $a^{b mod φ (n)}$ ；扩展欧拉在指数够大时要额外 $+ φ (n)$ 。这个 $+ φ (n)$ 是处理不互质情形的关键修正。

为什么需要 $+ φ (n)$ （直觉）

当 $g cd (a, n) \neq = 1$ 时， $a$ 的幂在模 n 下的序列不是纯循环，而是”先有一段不循环的前缀，再进入循环”（像字母 ρ 的形状）。 $+ φ (n)$ 保证你把指数推到过了前缀、稳定进入循环段之后再取模，从而结果正确。

例子（不互质情形）

求 $2^{100} mod 12$ 。注意 $g cd (2, 12) = 2 \neq = 1$ ，不能用普通欧拉。

$φ (12) = 4$
$b = 100 \geq φ (12) = 4$ ，用扩展欧拉：指数变成 $(100 mod 4) + 4 = 0 + 4 = 4$
$2^{100} \equiv 2^{4} = 16 \equiv 4 (mod 12)$

验证： $2^{4} = 16 \equiv 4$ ， $2^{5} = 32 \equiv 8$ ， $2^{6} = 64 \equiv 4$ ……从 $2^{2} = 4$ 起进入 $4, 8$ 循环， $2^{100}$ 确实 $\equiv 4$ ✓ （若错用普通欧拉 $2^{100 mod 4} = 2^{0} = 1$ ，得 1，错误！这就是为什么必须用扩展版。）

幂塔应用（一瞥）

算 $2^{2^{2^{2}}} mod n$ 这类幂塔，从最外层往里递归套用扩展欧拉：外层模 n 用 $φ (n)$ ，再内层模 $φ (n)$ 用 $φ (φ (n))$ …… $φ$ 反复迭代会快速降到 1，递归自然终止。这是竞赛幂塔题的标准解法。

⑥a Lucas 定理 (Lucas’ Theorem)

解决什么

算组合数取模质数 $(k n) mod p$ ，当 n、k 巨大（比如 $1 0^{18}$ ）而 p 较小（比如 $1 0^{9} + 7$ 以内的质数）时。

定理内容

把 n、k 写成 p 进制 (base-p)： $n = (n_{m} \dots n_{1} n_{0})_{p}$ ， $k = (k_{m} \dots k_{1} k_{0})_{p}$ 。则：

$(k n) \equiv \prod_{i = 0}^{m} (k _{i} n _{i}) (mod p)$

即”各数位的组合数之积”。每个 $(k _{i} n _{i})$ 里 $n_{i}, k_{i} < p$ 都很小，直接算。

附带推论：若某一位 $k_{i} > n_{i}$ ，则 $(k _{i} n _{i}) = 0$ ，整个 $(k n) \equiv 0 (mod p)$ 。

例子

求 $(3 10) mod 3$ 。

$10 = (101)_{3}$ ， $3 = (010)_{3}$
逐位： $(0 1) (1 0) (0 1) = 1 \times 0 \times 1 = 0$
所以 $(3 10) \equiv 0 (mod 3)$

验证： $(3 10) = 120 = 40 \times 3 \equiv 0 (mod 3)$ ✓

用途

组合计数题里 n 极大时的标准武器。配合 CRT 还能扩展到模合数（先对每个质因子用 Lucas，再 CRT 合并）。

⑥b 线性筛求欧拉函数 (Linear Sieve for Totient)

解决什么

一次性求出 $φ (1), φ (2), \dots, φ (n)$ 一整片， $O (n)$ 。比逐个套公式快得多，是数论题预处理标配。

原理

线性筛 (linear sieve / Euler sieve) 在筛质数的同时，利用 $φ$ 的两条性质递推：

p 是质数： $φ (p) = p - 1$
若 $p ∣ i$ ： $φ (i \cdot p) = φ (i) \cdot p$ （p 已是 i 的因子，不增新质因子）
若 $p ∤ i$ ： $φ (i \cdot p) = φ (i) \cdot (p - 1)$ （积性，p 是新质因子）

每个合数只被它的最小质因子筛一次，所以总复杂度 $O (n)$ 。

代码（含批量逆元、扩展欧拉、Lucas、线性筛——一次给全）

# ===== ⑤ 扩展欧拉定理 =====
from sympy import totient
def ext_euler_pow(a, b, n):
    phi = int(totient(n))
    if b < phi:
        return pow(a, b, n)
    return pow(a, b % phi + phi, n)   # 大指数 +phi 修正
 
print(ext_euler_pow(2, 100, 12))      # 4（不互质，普通欧拉会错）
 
# ===== ④ 批量逆元 O(n) =====
def batch_inverse(n, p):
    inv = [0] * (n + 1)
    inv[1] = 1
    for i in range(2, n + 1):
        inv[i] = (-(p // i) * inv[p % i]) % p
    return inv
print(batch_inverse(6, 7))            # [0,1,4,5,2,3,6]
 
# ===== ⑥a Lucas 定理 =====
def comb_small(n, k, p):              # 小组合数 mod p
    if k > n: return 0
    num = den = 1
    for i in range(k):
        num = num * (n - i) % p
        den = den * (i + 1) % p
    return num * pow(den, p - 2, p) % p
def lucas(n, k, p):
    if k == 0: return 1
    return comb_small(n % p, k % p, p) * lucas(n // p, k // p, p) % p
print(lucas(10, 3, 3))                # 0
 
# ===== ⑥b 线性筛欧拉函数 O(n) =====
def sieve_phi(n):
    phi = list(range(n + 1))
    primes = []
    is_comp = [False] * (n + 1)
    for i in range(2, n + 1):
        if not is_comp[i]:
            primes.append(i)
            phi[i] = i - 1
        for p in primes:
            if i * p > n: break
            is_comp[i * p] = True
            if i % p == 0:
                phi[i * p] = phi[i] * p        # 情况 2
                break
            else:
                phi[i * p] = phi[i] * (p - 1)  # 情况 3
    return phi
print(sieve_phi(12))   # [0,1,1,2,2,4,2,6,4,6,4,10,4]

库安装方式（用到 sympy 的 totient；④⑥纯标准库无需安装）：

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

补全后的 Stage 1–3 完整地图

阶段	原有核心	本次补全
Stage 1	同余、剩余系、 $φ$ 入门	Wilson 定理、环/群视角 $Z / n Z$
Stage 2	扩展欧几里得、逆元、线性同余	多元线性同余、批量逆元 $O (n)$
Stage 3	快速幂、费马、欧拉、CRT	扩展欧拉定理、Lucas 定理、线性筛 $φ$

我的观点：这六个补充里，分量最重、最该内化的是两个——扩展欧拉定理和环/群视角，而且它们的重要性是不同性质的。

扩展欧拉是实战补丁：它堵上了”不互质就不能降幂”这个真实的洞。你以后碰到 $2^{100} mod 12$ 这种底数和模数共因子的情况（密码学和竞赛里都常见），没有它就会算错。我建议你把那个例子（普通欧拉得 1、扩展欧拉得 4、真值是 4）记牢——这个”错与对的对比”比记公式管用。

而环/群视角是认知升维：它不教你算任何新东西，却悄悄改变你”看”模运算的方式。在补这一节之前，欧拉定理对你是一条要记的公式 $a^{φ (n)} \equiv 1$ ；补完之后，它会变成一句几乎不需要记的废话——“群里任何元素自乘’群的大小’次必然回到单位元”。这种”把一堆孤立公式压缩成一个统一原理”的体验，正是数学威力的核心。我特意把它安排在进 Stage 4 之前，因为 Stage 4 的原根、离散对数全部建立在” $(Z / n Z)^{*}$ 是群”这个认知上——你现在把这个视角焐热，下一阶段会顺得不可思议。

其余四个（Wilson、多元同余、批量逆元、Lucas、线性筛）我的态度是”知道、能查、用时会”即可，不必背。它们是工具箱里的专用扳手，遇到对应的螺丝再拿出来，平时不用占用你的记忆。

关键提醒 (Caveats)：

扩展欧拉的 $+ φ (n)$ 只在 $b \geq φ (n)$ 时加；小指数直接算，别画蛇添足
Lucas 定理要求模数是质数；合数要拆质因子分别 Lucas 再 CRT
批量逆元的递推只对质数模成立（用到了 $p mod i$ 的可逆性）
环/群视角是概念工具，本身不产生计算，别期待它”算出”什么——它的价值是让你理解为什么那些公式成立
本次代码用到 sympy 的 totient，安装：pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

现在 Stage 1–3 真正无死角了。要不要我出一套针对这六个补充点的小测验（延续 PDF 试卷 + 答案册格式）巩固一下，还是直接进 Stage 4：阶与原根 + 二次剩余 + 离散对数？****

My Vault

Explorer

3.5 补充

横向补全：Stage 1–3 的全部缺口（详细版）

补 Stage 1

① 威尔逊定理 (Wilson’s Theorem)

内容

为什么成立（证明思路）

例子

用途与陷阱

② 环视角：Z/nZ 与 (Z/nZ)∗

Z/nZ 是一个环 (ring)

(Z/nZ)∗ 是一个群 (group)

为什么这个视角重要

例子

补 Stage 2

③ 多元线性同余 / 线性丢番图方程 (Multivariable Linear Congruence)

问题形式

有解条件与求法

完整例子

几何直觉

④ 批量求逆元 (Batch Modular Inverse)

问题

递推公式（线性求逆）

为什么成立（推导）

例子（p=7，求 1∼6 的逆元）

补 Stage 3

⑤ 扩展欧拉定理 (Extended Euler’s Theorem) ★最重要的补充

解决什么

定理内容（三种情况）

为什么需要 +φ(n)（直觉）

例子（不互质情形）

幂塔应用（一瞥）

⑥a Lucas 定理 (Lucas’ Theorem)

解决什么

定理内容

例子

用途

⑥b 线性筛求欧拉函数 (Linear Sieve for Totient)

解决什么

原理

代码（含批量逆元、扩展欧拉、Lucas、线性筛——一次给全）

补全后的 Stage 1–3 完整地图

Graph View

Table of Contents

Backlinks

② 环视角： $Z / n Z$ 与 $(Z / n Z)^{*}$

$Z / n Z$ 是一个环 (ring)

$(Z / n Z)^{*}$ 是一个群 (group)

例子（ $p = 7$ ，求 $1 \sim 6$ 的逆元）

为什么需要 $+ φ (n)$ （直觉）