数论基础（模运算·素数·欧拉函数）

openSource
约 23 分钟阅读

阅读量:8次
数论
目标：给出系统、可复用的数学原理与证明纲要 + 典型算法模板与例题解析，覆盖模运算、素数理论与欧拉函数。

1. 同余与模运算（Modular Arithmetic）

1.1 同余的定义与等价关系

  • 定义：若整数 $a,b,n$ 且 $n>0$，当且仅当 $n\mid (a-b)$ 时，记 $a\equiv b\pmod n$。
  • 等价关系：反身、对称、传递均成立；因此在 $\mathbb{Z}$ 上诱导出等价类 —— 同余类。
  • 商结构：同余类集合 $\mathbb{Z}/n\mathbb{Z}$ 在加法、乘法下构成环；其可逆元集合记作 $\mathbb{Z}_n^\times=U(n)$，在乘法下成群，阶为 $\varphi(n)$。

1.2 基本性质与常见陷阱

  • 兼容性：若 $a\equiv b$, $c\equiv d\ (\bmod\ n)$，则 $a\pm c\equiv b\pm d$, $ac\equiv bd\ (\bmod\ n)$。
  • 幂：$a\equiv b\Rightarrow a^k\equiv b^k\ (\bmod\ n)$。
  • 消去律的前提：若 $ac\equiv bc\ (\bmod\ n)$，欲得 $a\equiv b$，需 $\gcd(c,n)=1$。
  • 负数取模：实现时可用正规化 $((x\%n)+n)\%n$。

1.3 线性同余方程

形如 $ax\equiv b\pmod n$。令 $d=\gcd(a,n)$。

  • 可解条件：$d\mid b$。
  • 解的个数：若可解，则有 恰好 $d$ 个不同解模 $n$。
  • 构造法：化为 $\frac{a}{d} x\equiv \frac{b}{d}\pmod{\frac{n}{d}}$，其中 $\gcd(\frac{a}{d},\frac{n}{d})=1$，解 $x_0$ 后给出通解 $x\equiv x_0+ t\cdot \frac{n}{d}$。

1.4 扩展欧几里得与模逆

  • Bézout 定理：存在整数 $x,y$ 使 $ax+by=\gcd(a,b)$。
  • 扩展欧几里得（exgcd）：在求 $\gcd$ 的同时返回系数 $(x,y)$。若 $\gcd(a,n)=1$，则 $x\equiv a^{-1}\pmod n$。
  • 复杂度：$O(\log(\min{a,b}))$。

1.5 快速幂与模幂

  • 平方-乘法：将指数二进制展开，迭代"平方+按位乘"。复杂度 $O(\log e)$。
  • 应用：计算 $a^e\bmod n$、Miller–Rabin、RSA 等。

1.6 中国剩余定理（CRT）

  • 定理：若 $n_1,\dots,n_k$ 两两互素，令 $N=\prod n_i$，则同余组 $x\equiv a_i\ (\bmod\ n_i)$ 存在唯一解模 $N$。
  • 构造：$N_i=N/n_i$，求 $M_i\equiv N_i^{-1}\ (\bmod\ n_i)$，解为
    $$x\equiv \sum_{i=1}^k a_i N_i M_i \pmod N.$$
  • 证明思路 A（构造）：对每个 $i$，有 $N_iM_i\equiv 1\ (\bmod\ n_i)$ 且 $\equiv 0\ (\bmod\ n_j)$（$j\ne i$），线性组合即解。
  • 证明思路 B（同构）：利用环同构 $\mathbb{Z}/N\cong\prod \mathbb{Z}/n_i$。
  • 推论：$U(N)\cong\prod U(n_i)$，并据此得 $\varphi$ 的乘法性（见 §3）。

1.7 乘法阶与循环

  • 定义：若 $\gcd(a,n)=1$，$\operatorname{ord}_n(a)$ 为最小 $t>0$ 使 $a^t\equiv1\pmod n$。
  • 性质：$\operatorname{ord}_n(a)\mid \lambda(n)$，亦 $\mid\varphi(n)$。若 $a^k\equiv1$ 则 $\operatorname{ord}_n(a)\mid k$。
  • 应用：周期分析、原根判定、离散对数算法复杂度估算。

2. 素数理论基础（Prime Theory）

2.1 基本概念与唯一分解

  • 素数：仅有 1 与自身为正因子的整数（约定 1 非素）。

  • 算术基本定理：每个 $n\ge2$ 可唯一分解为素数乘积（忽略因子顺序）。

    • 证明要点：存在性用最小反例法；唯一性用素数整除性质（若 $p\mid ab$ 则 $p\mid a$ 或 $p\mid b$）。

2.2 经典命题

  • Euclid：素数无穷多。证法：若仅有限个素数乘积加 1 得到新数，不被任何已知素数整除。
  • Bertrand 选言：对 $n\ge2$，存在素数 $p\in(n,2n)$。
  • 勒让德公式：$\nu_p(n!)=\sum_{i\ge1}\left\lfloor \frac{n}{p^i}\right\rfloor$。
  • 二项式系数模素数：$\binom{p}{k}\equiv0\ (\bmod\ p)$（$1\leq k\leq p-1$）。

2.3 原根与循环群

  • 事实：$\mathbb{Z}_p^\times$（素模的单位群）是循环群，存在原根 $g$。
  • 非素模的存在性：仅在 $n=2,4,p^k,2p^k$（$p$ 奇素）时 $\mathbb{Z}_n^\times$ 循环。
  • 离散对数：给定 $g,a$，求 $x$ 使 $g^x\equiv a$；对大素数模难（见密码学应用）。

2.4 素性测试与分解（原理速览）

  • Fermat 检验：若 $a^{p-1}\not\equiv1\ (\bmod\ p)$ 则合数；反之未必（伪素数、Carmichael 数）。

  • Miller–Rabin（随机化）：令 $n-1=2^s d$（$d$ 奇）。若对某底 $a$ 既不满足 $a^d\equiv1$ 又所有 $a^{2^r d}\not\equiv-1$（$0\le r<s$），则 $n$ 合数；否则"可能素"。

    • 数学要点：若 $n$ 为奇素，则 $x^2\equiv1$ 的非平凡根仅 $\pm1$；利用平方链排除。
  • 分解算法：Pollard $\rho$、ECM、NFS（数域筛）等；安全参数通常由最优分解算法复杂度界定。

3. 欧拉函数与相关定理（Euler's Totient）

3.1 定义与基本公式

  • 定义：$\varphi(n)=|\{1\le k\le n\mid \gcd(k,n)=1\}|$。

  • 素幂：$\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$。

    • 证明：在 $\{1,\dots,p^k\}$ 中，恰有 $p^{k-1}$ 个能被 $p$ 整除，其余互素。

  • 乘法性（互素乘法）：若 $\gcd(m,n)=1$，则 $\varphi(mn)=\varphi(m)\varphi(n)$。

    • 证明法 A：CRT 同构 $U(mn)\cong U(m)\times U(n)$ ⇒ 阶相乘。
    • 证明法 B：容斥/计数：$\varphi(n)=n\prod_{p\mid n}\bigl(1-\frac{1}{p}\bigr)$。
  • 一般公式：若 $n=\prod p_i^{e_i}$，则 $\displaystyle \varphi(n)=n\prod_i\left(1-\frac{1}{p_i}\right)$。

3.2 费马小定理与欧拉定理

  • 费马小定理（FLT）：若 $p$ 素且 $p\nmid a$，则 $a^{p-1}\equiv1\ (\bmod\ p)$。

    • 证明 1（群论）：$\mathbb{Z}_p^\times$ 为阶 $p-1$ 的群，拉格朗日定理。
    • 证明 2（排列）：$\{a,2a,\dots,(p-1)a\}$ 模 $p$ 为 $\{1,\dots,p-1\}$ 的排列 ⇒ 积相等。
    • 证明 3（组合）：利用 $\binom{p}{k}\equiv0$。

  • 欧拉定理：若 $\gcd(a,n)=1$，则 $a^{\varphi(n)}\equiv1\ (\bmod\ n)$。

    • 证明 1（群论）：$a\in U(n)$，由拉格朗日定理得结论。
    • 证明 2（排列/乘积法）：$a$ 与 $U(n)$ 中每元相乘诱导置换。

3.3 卡迈克尔函数与最小指数

  • 定义：$\lambda(n)$ 为满足 $a^{\lambda(n)}\equiv1\ (\bmod\ n)$（所有 $\gcd(a,n)=1$）的最小正整数。
  • 性质：$\lambda(n)\mid\varphi(n)$；对质幂 $p^k$（$p\ge3$）有 $\lambda(p^k)=p^{k-1}(p-1)$；对 $2^k$（$k\ge3$）有 $\lambda(2^k)=2^{k-2}$。一般 $\lambda$ 对应 $U(n)$ 的指数，且 $\lambda\bigl(\operatorname{lcm}(m,n)\bigr)=\operatorname{lcm}(\lambda(m),\lambda(n))$。
  • 应用：给出比 $\varphi(n)$ 更紧的幂指数上界；在 RSA 正确性分析与优化中常用 $\lambda(n)=\operatorname{lcm}(p-1,q-1)$。

3.4 求和恒等式与反演

  • 恒等式：$\displaystyle \sum_{d\mid n} \varphi(d)=n$。

    • 证明：将 $\{1,\dots,n\}$ 按 $\gcd(k,n)=d$ 分类，或用群作用的轨道计数。
  • Möbius 反演：由上式得 $\displaystyle \varphi(n)=\sum_{d\mid n} \mu(d)\cdot \frac{n}{d}$，其中 $\mu$ 为 Möbius 函数。

4. 例题精讲

例 1（线性同余）

求解 $35x\equiv10\pmod{50}$。

  • $d=\gcd(35,50)=5\mid10$ ⇒ 可解，共有 5 个解。
  • 化简：$7x\equiv2\pmod{10}$。求 $7^{-1}\equiv 3\pmod{10}$（因 $7\cdot3=21\equiv1$）。得 $x\equiv 6\pmod{10}$。
  • 通解（模 50）：$x\equiv 6,16,26,36,46$。

例 2（CRT）

$x\equiv2\pmod3,\ x\equiv3\pmod5,\ x\equiv2\pmod7$。

  • $N=105$，$N_1=35,M_1\equiv35^{-1}\equiv2\ (\bmod \3)$；$N_2=21,M_2\equiv1\ (\bmod \5)$；$N_3=15,M_3\equiv1\ (\bmod \7)$。
  • $x\equiv 2\cdot35\cdot2+3\cdot21\cdot1+2\cdot15\cdot1=140+63+30=233\equiv 23\pmod{105}$。

例 3（$\varphi(n)$ 计算）

设 $n=2^3\cdot3^2\cdot5$。则
$$\varphi(n)=n\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)=360\cdot\frac{1}{2}\cdot\frac{2}{3}\cdot\frac{4}{5}=96.$$

例 4（FLT 与欧拉定理）

求 $2^{100}\bmod101$。$101$ 素，$2^{100}\equiv1\pmod{101}$。

例 5（Miller–Rabin 见证）

取 $n=561$（Carmichael 数），$n-1=2^4\cdot35$。以 $a=2$ 检验：$2^{35}\equiv 263\not\equiv1,-1$，平方链不出现 $-1$，判合数。

5. 常见误区与边界情形

  • 错误消去：$ac\equiv bc$ 未必可消去 $c$，除非 $\gcd(c,n)=1$。
  • 模逆不存在：若 $\gcd(a,n)\ne1$ 则 $a^{-1}$ 不存在。
  • 指数取模：$a^{b}\bmod n$ 仅能对底数取模，不能把指数"取模"直接替换（除非涉及阶与 $\lambda(n)$ 的同余推理）。
  • 负模与语言实现差异：注意 C/C++、Python 的取模约定差别，统一正规化。

6. 算法模板（伪代码）

扩展欧几里得

function exgcd(a, b):
    if b == 0: return (a, 1, 0)
    (d, x1, y1) = exgcd(b, a % b)
    return (d, y1, x1 - (a//b)*y1)

模逆（exgcd 版）

function inv_mod(a, n):
    (d, x, _) = exgcd(a, n)
    if d != 1: error "inverse doesn't exist"
    return (x % n + n) % n

快速幂（迭代版）

function pow_mod(a, e, n):
    r = 1; a %= n
    while e > 0:
        if (e & 1): r = (r * a) % n
        a = (a * a) % n
        e >>= 1
    return r

CRT（两模合并，可扩展）

# Solve x ≡ a1 (mod m1), x ≡ a2 (mod m2), require gcd(m1,m2)=1
function crt_merge(a1, m1, a2, m2):
    (d, x, y) = exgcd(m1, m2)
    if d != 1: error "moduli not coprime"
    t = ((a2 - a1) * x) % m2
    x0 = (a1 + t * m1) % (m1 * m2)
    return (x0, m1 * m2)

Miller–Rabin（核心）

function is_probable_prime(n):
    if n < 4: return n in {2,3}
    if n % 2 == 0: return false
    # write n-1 = 2^s * d
    s = 0; d = n - 1
    while d % 2 == 0: s += 1; d //= 2
    for a in BASES:  # 选定若干底
        if a % n == 0: continue
        x = pow_mod(a, d, n)
        if x == 1 or x == n-1: continue
        repeat = false
        for r in range(1, s):
            x = (x * x) % n
            if x == n-1: repeat = true; break
        if not repeat: return false
    return true
注：针对 64 位整数的确定性底集合可选 {2,3,5,7,11,13,17} 等（具体集合依实现与范围）。

7. 学习清单参考

  • 教科书：Niven–Zuckerman–Montgomery《An Introduction to the Theory of Numbers》；Apostol《Introductory Analytic Number Theory》。
  • 算法与实现：Crandall–Pomerance《Prime Numbers: A Computational Perspective》；GMP/NTL 文档。
  • 竞赛/工程速查：CP-algorithms、TAOCP vol.2 第 4 章。

添加新评论