数论思维导图

# 《数论思维导图》

## I. 基础概念 (Fundamental Concepts)

### A. 整数 (Integers)

*   定义：正整数、负整数和零的集合 (..., -2, -1, 0, 1, 2, ...)
*   符号：ℤ
*   运算：加法、减法、乘法、除法 (Division with remainder)
*   性质：
    *   封闭性：加减乘运算结果仍为整数
    *   交换律、结合律、分配律

### B. 自然数 (Natural Numbers)

*   定义：非负整数的集合 (0, 1, 2, 3, ...) (不同定义可能不包含0)
*   符号：ℕ
*   公理：Peano公理
*   性质：有序性、无限性

### C. 整除 (Divisibility)

*   定义：a | b (a divides b)  <=>  存在整数 k, 使得 b = ak
*   性质：
    *   传递性：若 a | b 且 b | c，则 a | c
    *   线性组合：若 a | b 且 a | c，则对于任意整数 x, y, a | (bx + cy)
*   相关概念：
    *   因子 (Factor/Divisor)：a | b, 则 a 是 b 的因子
    *   倍数 (Multiple)：b = ak, 则 b 是 a 的倍数

### D. 质数与合数 (Prime and Composite Numbers)

*   质数：只有1和本身两个正因数的数 (注意：1既不是质数也不是合数)
    *   例子：2, 3, 5, 7, 11, 13, ...
    *   无穷性：质数有无穷多个 (欧几里得证明)
*   合数：除了1和本身以外还有其他正因数的数
    *   例子：4, 6, 8, 9, 10, 12, ...
*   分解定理：
    *   算术基本定理：任何大于1的整数都可以唯一地分解为一系列质因数的乘积 (忽略质因数的顺序)

## II. 重要定理与算法 (Important Theorems and Algorithms)

### A. 欧几里得算法 (Euclidean Algorithm)

*   目的：求最大公约数 (Greatest Common Divisor, GCD)
*   原理：gcd(a, b) = gcd(b, a mod b) (辗转相除法)
*   实现：递归或迭代
*   扩展欧几里得算法 (Extended Euclidean Algorithm):  求 ax + by = gcd(a, b) 的一组解 (x, y)
    *   应用：求解线性同余方程, 模逆元

### B. 模运算 (Modular Arithmetic)

*   定义：a ≡ b (mod m)  <=>  m | (a - b) (a congruent to b modulo m)
*   性质：
    *   加法、减法、乘法可直接进行模运算
    *   (a + b) mod m = (a mod m + b mod m) mod m
    *   (a * b) mod m = (a mod m * b mod m) mod m
*   费马小定理 (Fermat's Little Theorem): 若 p 为质数，且 a 与 p 互质，则 a^(p-1) ≡ 1 (mod p)
*   欧拉定理 (Euler's Theorem): 若 a 与 n 互质，则 a^φ(n) ≡ 1 (mod n), 其中 φ(n) 是欧拉函数
*   中国剩余定理 (Chinese Remainder Theorem, CRT):  求解同余方程组 x ≡ a_i (mod m_i)  (m_i 两两互质)

### C. 素性测试 (Primality Tests)

*   试除法 (Trial Division): 检验 n 能否被小于等于 sqrt(n) 的所有质数整除
*   Miller-Rabin 素性测试: 基于费马小定理和二次探测定理的概率性算法
*   AKS 素性测试: 第一个被证明的多项式时间复杂度确定性素性测试算法

### D. 积性函数 (Multiplicative Function)

*   定义: 若 f(mn) = f(m)f(n)  当 m, n 互质时成立，则称 f(n) 为积性函数
*   完全积性函数: 若 f(mn) = f(m)f(n)  对所有 m, n 都成立，则称 f(n) 为完全积性函数
*   常见积性函数: 欧拉函数 φ(n), 除数函数 σ(n), 莫比乌斯函数 μ(n)
*   线性筛法 (Sieve of Eratosthenes): 高效地计算多个数的积性函数值

## III. 数论应用 (Applications of Number Theory)

### A. 密码学 (Cryptography)

*   RSA 算法: 基于大数分解的困难性
*   椭圆曲线密码学 (Elliptic Curve Cryptography, ECC): 基于椭圆曲线上的离散对数问题
*   Diffie-Hellman 密钥交换: 基于离散对数问题

### B. 编码理论 (Coding Theory)

*   纠错码: 基于数论的代数结构
*   线性码

### C. 随机数生成 (Random Number Generation)

*   线性同余发生器 (Linear Congruential Generator, LCG)

### D. 算法优化 (Algorithm Optimization)

*   模运算优化: 避免大数运算溢出
*   数论分块: 优化计算涉及除法的和式

## IV. 进阶主题 (Advanced Topics)

### A. 狄利克雷卷积 (Dirichlet Convolution)

*   定义： (f * g)(n) = Σ_{d|n} f(d)g(n/d)
*   性质：交换律、结合律、分配律
*   应用：简化数论函数求和

### B. 莫比乌斯反演 (Möbius Inversion)

*   公式：如果 g(n) = Σ_{d|n} f(d)，那么 f(n) = Σ_{d|n} μ(d)g(n/d)
*   应用：解决与因子相关的求和问题

### C. 二次剩余 (Quadratic Residue)

*   定义：如果存在 x 使得 x^2 ≡ a (mod p)，则称 a 是模 p 的二次剩余
*   勒让德符号 (Legendre Symbol):  (a/p) = 1 如果 a 是模 p 的二次剩余; (a/p) = -1 如果 a 不是模 p 的二次剩余; (a/p) = 0 如果 p | a

### D. 原根 (Primitive Root)

*   定义：如果 g 是模 n 的原根，那么 g^1, g^2, ..., g^φ(n) 模 n 两两不同余
*   应用：计算离散对数

《数论思维导图》

I. 基础概念 (Fundamental Concepts)

A. 整数 (Integers)

定义：正整数、负整数和零的集合 (..., -2, -1, 0, 1, 2, ...)
符号：ℤ
运算：加法、减法、乘法、除法 (Division with remainder)
性质：
- 封闭性：加减乘运算结果仍为整数
- 交换律、结合律、分配律

B. 自然数 (Natural Numbers)

定义：非负整数的集合 (0, 1, 2, 3, ...) (不同定义可能不包含0)
符号：ℕ
公理：Peano公理
性质：有序性、无限性

C. 整除 (Divisibility)

定义：a | b (a divides b) <=> 存在整数 k, 使得 b = ak
性质：
- 传递性：若 a | b 且 b | c，则 a | c
- 线性组合：若 a | b 且 a | c，则对于任意整数 x, y, a | (bx + cy)
相关概念：
- 因子 (Factor/Divisor)：a | b, 则 a 是 b 的因子
- 倍数 (Multiple)：b = ak, 则 b 是 a 的倍数

D. 质数与合数 (Prime and Composite Numbers)

质数：只有1和本身两个正因数的数 (注意：1既不是质数也不是合数)
- 例子：2, 3, 5, 7, 11, 13, ...
- 无穷性：质数有无穷多个 (欧几里得证明)
合数：除了1和本身以外还有其他正因数的数
- 例子：4, 6, 8, 9, 10, 12, ...
分解定理：
- 算术基本定理：任何大于1的整数都可以唯一地分解为一系列质因数的乘积 (忽略质因数的顺序)

II. 重要定理与算法 (Important Theorems and Algorithms)

A. 欧几里得算法 (Euclidean Algorithm)

目的：求最大公约数 (Greatest Common Divisor, GCD)
原理：gcd(a, b) = gcd(b, a mod b) (辗转相除法)
实现：递归或迭代
扩展欧几里得算法 (Extended Euclidean Algorithm): 求 ax + by = gcd(a, b) 的一组解 (x, y)
- 应用：求解线性同余方程, 模逆元

B. 模运算 (Modular Arithmetic)

定义：a ≡ b (mod m) <=> m | (a - b) (a congruent to b modulo m)
性质：
- 加法、减法、乘法可直接进行模运算
- (a + b) mod m = (a mod m + b mod m) mod m
- (a b) mod m = (a mod m b mod m) mod m
费马小定理 (Fermat's Little Theorem): 若 p 为质数，且 a 与 p 互质，则 a^(p-1) ≡ 1 (mod p)
欧拉定理 (Euler's Theorem): 若 a 与 n 互质，则 a^φ(n) ≡ 1 (mod n), 其中 φ(n) 是欧拉函数
中国剩余定理 (Chinese Remainder Theorem, CRT): 求解同余方程组 x ≡ a_i (mod m_i) (m_i 两两互质)

C. 素性测试 (Primality Tests)

试除法 (Trial Division): 检验 n 能否被小于等于 sqrt(n) 的所有质数整除
Miller-Rabin 素性测试: 基于费马小定理和二次探测定理的概率性算法
AKS 素性测试: 第一个被证明的多项式时间复杂度确定性素性测试算法

D. 积性函数 (Multiplicative Function)

定义: 若 f(mn) = f(m)f(n) 当 m, n 互质时成立，则称 f(n) 为积性函数
完全积性函数: 若 f(mn) = f(m)f(n) 对所有 m, n 都成立，则称 f(n) 为完全积性函数
常见积性函数: 欧拉函数 φ(n), 除数函数 σ(n), 莫比乌斯函数 μ(n)
线性筛法 (Sieve of Eratosthenes): 高效地计算多个数的积性函数值

III. 数论应用 (Applications of Number Theory)

A. 密码学 (Cryptography)

RSA 算法: 基于大数分解的困难性
椭圆曲线密码学 (Elliptic Curve Cryptography, ECC): 基于椭圆曲线上的离散对数问题
Diffie-Hellman 密钥交换: 基于离散对数问题

B. 编码理论 (Coding Theory)

纠错码: 基于数论的代数结构
线性码

C. 随机数生成 (Random Number Generation)

线性同余发生器 (Linear Congruential Generator, LCG)

D. 算法优化 (Algorithm Optimization)

模运算优化: 避免大数运算溢出
数论分块: 优化计算涉及除法的和式

IV. 进阶主题 (Advanced Topics)

A. 狄利克雷卷积 (Dirichlet Convolution)

定义： (f * g)(n) = Σ_{d|n} f(d)g(n/d)
性质：交换律、结合律、分配律
应用：简化数论函数求和

B. 莫比乌斯反演 (Möbius Inversion)

公式：如果 g(n) = Σ{d|n} f(d)，那么 f(n) = Σ{d|n} μ(d)g(n/d)
应用：解决与因子相关的求和问题

C. 二次剩余 (Quadratic Residue)

定义：如果存在 x 使得 x^2 ≡ a (mod p)，则称 a 是模 p 的二次剩余
勒让德符号 (Legendre Symbol): (a/p) = 1 如果 a 是模 p 的二次剩余; (a/p) = -1 如果 a 不是模 p 的二次剩余; (a/p) = 0 如果 p | a

D. 原根 (Primitive Root)

定义：如果 g 是模 n 的原根，那么 g^1, g^2, ..., g^φ(n) 模 n 两两不同余
应用：计算离散对数

上一个主题：西游记思维导图下一个主题：动漫思维导图