🔍 数论进阶

1.1 模的定义与基本运算 Definition and Basic Operations

给定正整数 m，若 a 和 b 除以 m 的余数相同，则称 a 与 b 对模 m 同余，记作：

基本运算规则：

• 加法：若 a ≡ b (mod m)，c ≡ d (mod m)，则 a + c ≡ b + d (mod m)
• 乘法：若 a ≡ b (mod m)，c ≡ d (mod m)，则 ac ≡ bd (mod m)
• 幂运算：若 a ≡ b (mod m)，则 a^k ≡ b^k (mod m)，对任意正整数 k 成立

Addition, multiplication, and exponentiation all preserve congruences. These rules are the foundation of all modular computation.

1.2 同余的性质 Properties of Congruences

同余关系具有以下重要性质（等价于整数环的性质）：

模的消去律（关键！）：

若 ac ≡ bc (mod m) 且 gcd(c, m) = d，则 a ≡ b (mod m/d)。

Cancellation in congruences requires dividing the modulus by gcd(c, m), not by m itself. This is a very common AMC 12 trick!

1.3 线性同余方程 Linear Congruences

形如 ax ≡ b (mod m) 的方程称为线性同余方程。

求解方法：

• 设 d = gcd(a, m)。若 d ∤ b，则无解。
• 若 d | b，将方程两边同时除以 d：
  (a/d)x ≡ (b/d) (mod m/d)
• 此时 gcd(a/d, m/d) = 1，可用扩展欧几里得算法求 (a/d) 的逆元，乘以 b/d 即得解。

扩展欧几里得算法求逆元：

求 a 在模 m 下的逆元，等价于求整数 x, y 使得 ax + my = gcd(a, m) = 1，此时 x 即为逆元。

2.1 Fermat小定理 Fermat's Little Theorem (FLT)

等价形式：对任意整数 a，a^p ≡ a (mod p)（包括 a ≡ 0 mod p 的情况）。

An equivalent form: a^p ≡ a (mod p) for all integers a (this version includes the case a ≡ 0 mod p).

典型应用：求大数的模 p 余数、质数判定、证明某些数不是质数。

例：求 7²⁰²⁵ mod 13。

解：13 是质数，7 ∤ 13。由 FLT：7¹² ≡ 1 (mod 13)。

2025 = 12 × 168 + 9，所以 7²⁰²⁵ = (7¹²)¹⁶⁸ × 7⁹ ≡ 1¹⁶⁸ × 7⁹ ≡ 7⁹ (mod 13)。

继续化简：7² ≡ 49 ≡ 10 (mod 13)，7⁴ ≡ 10² ≡ 9 (mod 13)，7⁸ ≡ 9² ≡ 81 ≡ 3 (mod 13)，所以 7⁹ ≡ 7⁸ × 7 ≡ 3 × 7 = 21 ≡ 8 (mod 13)。

2.2 Euler定理 Euler's Theorem

其中 φ(n) 是 Euler φ 函数，表示 1 到 n 中与 n 互质的整数个数。

φ(n) 的计算公式：

• 若 n = p^k（p 为质数），φ(n) = p^k − p^k−1 = p^k(1 − 1/p)
• 若 n = p·q（p, q 为不同质数），φ(n) = (p−1)(q−1)
• 若 n = p₁^a1 · p₂^a2 · ...，则 φ(n) = n · ∏(1 − 1/p_i)

Euler's Theorem is a generalization of FLT. When n = p (prime), φ(p) = p − 1, so Euler's Theorem becomes FLT.

2.3 中国剩余定理 Chinese Remainder Theorem (CRT)

求解方法（构造法）：

设 M = m₁m₂⋯m_k，M_i = M/m_i，求 M_i 在模 m_i 下的逆元 t_i（即 M_it_i ≡ 1 (mod m_i)）。

则通解为：

简化版（两个方程时）：

解 x ≡ a (mod m)，x ≡ b (mod n)（其中 m, n 互质）：

x = a + m·[(b − a) · m⁻¹ mod n]，取最小非负解即得。

2.4 Wilson定理 Wilson's Theorem

这是质数判定的充要条件（比 FLT 的逆命题更强）。

重要推论：

• 若 (p − 1)! ≡ −1 (mod p)，则 p 一定是质数（但这计算量太大，不适合做大数判定）。
• 在模 p 下，1, 2, …, p−1 的乘法逆元是配对的：i · (p−i) ≡ −1 (mod p)。

Wilson定理的推论：对于质数 p > 2，(p−1)! ≡ 1 · 2 · ... · (p−1) ≡ −1 (mod p)，且在配对 (1, p−1), (2, p−2), ... 时，每对的乘积 ≡ −1 (mod p)。

3.1 阶（Order）的概念 Order of an Integer

基本性质：

• ord_n(a) 总是 φ(n) 的约数（由 Euler 定理：a^φ(n) ≡ 1 mod n）
• 若 a^t ≡ 1 (mod n)，则 ord_n(a) | t
• 若 ord_n(a) = d，则 a¹, a², …, a^d 在模 n 下两两不同

The order always divides φ(n). This is a powerful tool for solving problems about cycles and periodicity in modular arithmetic.

3.2 原根 Primitive Roots

原根的意义：从 g⁰, g¹, …, g^φ(n)−1 可以生成模 n 下所有与 n 互质的数。

原根的存在性：

重要性质：

• 若 g 是模 p 的原根（p 为质数），则 {g¹, g², …, g^p−1} 恰好构成模 p 乘法群的全部非零元素
• 模 p 的原根个数为 φ(p−1)

3.3 Legendre符号简介 Legendre Symbol

核心性质：

• 乘法性：(ab/p) = (a/p)(b/p)
• Euler判别法：(a/p) ≡ a^(p−1)/2 (mod p)
• 二次互反律（Quadratic Reciprocity）：若 p, q 为奇质数，则 (p/q)·(q/p) = (−1)^{((p−1)/2)·((q−1)/2)}

Legendre's symbol tells us whether a is a quadratic residue (a perfect square) modulo a prime p. The law of quadratic reciprocity relates (p/q) and (q/p).

3.4 Diophantine方程 Diophantine Equations

Diophantine 方程是指未知数只能取整数值的方程。AMC 12 中常见的类型包括：

① 线性Diophantine方程：ax + by = c

② Pell方程：x² − ny² = 1（n为非完全平方数）

Pell 方程总是有无穷多组正整数解。其最小解 (x₁, y₁) 可以通过连分数展开求得。

Pell's equation has infinitely many solutions, and all solutions can be generated from the minimal solution via recurrence relations.

③ 指数型Diophantine（如 a^x − b^y = c）

这类方程通常利用模运算来限制可能的解，再用枚举或因式分解求解。