Lagrange 定理在数论、几何、组合、密码、算法中的经典应用

Lagrange 定理（有限群的阶能被其子群的阶整除）是一条“计数利器”。它把“群的大小”与“子结构的存在性/不存在性”直接挂钩，因而在数论、几何、组合、密码、算法等多个领域都有“一句话就能秒杀”的经典应用。

Lagrange 定理=“把阶数当筛子”：

只要遇到“有限集合+封闭运算”，先用 |H| 必须整除 |G| 筛掉不可能，再对剩下的结构做精细分析——数论、密码、算法、几何皆如此。

1 费马小定理 & 欧拉定理

 定理：Lagrange |G| = φ(n)

 用法：把 (ℤ/nℤ)× 视为乘法群，元素 a 的阶必须整除 φ(n)

 结果：a^{φ(n)} ≡ 1 (mod n)，费马小定理是 n = p 的特例。

2 RSA 私钥存在性

 定理：Lagrange |G| = φ(n)

 用法：选 e 与 φ(n) 互素 ⇒ e 在 G 中有逆元 d

 结果：e·d ≡ 1 (mod φ(n))，保证解密还原。

3 Wilson 定理

 定理：Lagrange |G| = p−1 (p 素)

 用法：在 (ℤ/pℤ)× 中，所有元素成对互逆，仅 ±1 自逆

 结果：(p−1)! ≡ −1 (mod p)。

4 群阶判定“不可能”

 定理：Lagrange |H| | |G|

 用法：若 |G| = 15，任何真子群阶只能是 1,3,5,15

 结果：15 阶群必循环（因 3、5 互素，无 15 阶非循环可能）。

5 Sylow 存在性判定

 定理：Lagrange |G| = p^k·m (p∤m)

 用法：Sylow p-子群阶必须为 p^k（Lagrange 先导）

 结果：Sylow 定理第一断言“必存在 p^k 阶子群”。

6 魔方状态数计算

 定理：Lagrange |G| = |魔方合法转动群|

 用法：用 Lagrange 算正规子群 N，得 |G/N| = 2

 结果：合法状态 = 4.3×10¹⁹，而非 12!·2¹¹·3⁷。

7 几何对称点群分类

 定理：Lagrange |G| = 24, 48, 60 …

 用法：晶体点群子群链必须整除 24（立方）、48（八面）

 结果：230 空间群枚举得以系统化。

8 算法复杂度（离散对数）

 定理：Lagrange |G| = q (素)

 用法：Pohlig–Hellman 把 G 降阶到各 Sylow 子群

 结果：若 |G| 光滑，离散对数可指数级加速。

9 组合计数 Burnside 引理

 定理：Lagrange |G| = n

 用法：轨道大小必须整除 n，从而化简不动点计数

 结果：计数项链、化学异构体、图同构。