学习笔记

Appearance

组合数论：卢卡斯与库默尔（Combinatorial Number Theory） ​

核心定位

组合数论研究组合对象（二项式系数、Catalan 数、Stirling 数、分拆数等）的整除性与数论性质。Lucas 定理与 Kummer 定理是其中最核心的两个工具，前者刻画二项式系数模素数的取值，后者通过 $p$-adic 进位分析整除幂次。这些结果在 CMO、TST、IMO 等高档次竞赛中频繁出现，并与 整除与同余基础、数论函数与欧拉定理、二次剩余与阶 等形成完整知识网络。

一、二项式系数的整除性 ​

1.1 基本事实 ​

二项式系数的素因子

对素数 $p$与整数$0 \le k \le n$：

  • $p \mid \binom{p}{k}$当$1 \le k \le p-1$
  • $\binom{p^a}{k} \equiv 0 \pmod{p}$当$1 \le k \le p^a - 1$且$p^{a-1} \nmid k$（更精细见 Lucas）

1.2 Kummer 定理（进位法） ​

Kummer 定理（1975）

对素数 $p$与正整数$n \ge m \ge 0$，$\binom{n}{m}$中$p$的幂次$v_p\negthinspace\left(\binom{n}{m}\right)$等于$m$与$n - m$在$p$ 进制加法中产生的进位次数。

等价形式：$v_p\negthinspace\left(\binom{n}{m}\right) = \dfrac{s_p(m) + s_p(n-m) - s_p(n)}{p-1}$，其中 $s_p(n)$是$n$在$p$ 进制下各位数字之和。

Kummer 定理应用

求 $v_2\negthinspace\binom{100}{50}$。

解：$100 = 1100100_2$，$50 = 0110010_2$。$50 + 50 = 100$：

    0110010
  + 0110010
  --------
    1100100

逐位相加（自低位到高位）：

  • 第 0 位：$0 + 0 = 0$，无进位
  • 第 1 位：$1 + 1 = 2$，写 $0$进$1$（进位 1）
  • 第 2 位：$0 + 0 + 1 = 1$，无进位
  • 第 3 位：$0 + 0 = 0$，无进位
  • 第 4 位：$1 + 1 = 2$，写 $0$进$1$（进位 2）
  • 第 5 位：$1 + 1 + 1 = 3$，写 $1$进$1$（进位 3）
  • 第 6 位：$0 + 0 + 1 = 1$

共 $3$次进位，故$v_2\negthinspace\binom{100}{50} = 3$。

验证（用和公式）：$s_2(50) = 3$，$s_2(50) = 3$，$s_2(100) = 3$，$v_2 = (3+3-3)/(2-1) = 3$。✓

1.3 $v_p(n!)$ 的 Legendre 公式 ​

Legendre 公式

$$v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor = \frac{n - s_p(n)}{p - 1}$$

后一等式来自 $p$ 进制展开。

由 $v_p\negthinspace\binom{n}{m} = v_p(n!) - v_p(m!) - v_p((n-m)!)$ 立得 Kummer 定理。

$v_p(n!)$ 计算

求 $v_5(2024!)$。

解：$\left\lfloor 2024/5 \right\rfloor + \left\lfloor 2024/25 \right\rfloor + \left\lfloor 2024/125 \right\rfloor + \left\lfloor 2024/625 \right\rfloor + \left\lfloor 2024/3125 \right\rfloor + \cdots$ $= 404 + 80 + 16 + 3 + 0 = 503$。

二、Lucas 定理 ​

2.1 Lucas 定理 ​

Lucas 定理（1878）

设 $p$ 为素数，$n, m$为非负整数，将它们表为$p$ 进制： $$n = n_0 + n_1 p + \cdots + n_r p^r,\quad m = m_0 + m_1 p + \cdots + m_r p^r \quad (0 \le n_i, m_i \le p-1)$$ 则 $$\binom{n}{m} \equiv \prod_{i=0}^{r} \binom{n_i}{m_i} \pmod{p}$$ 其中约定 $\binom{a}{b} = 0$当$b > a$。

证明思路：用生成函数。在 $\mathbb{F}_p[x]$ 中，$(1+x)^p \equiv 1 + x^p \pmod p$（Freshman's dream），故 $$(1+x)^n = \prod_i (1+x)^{n_i p^i} \equiv \prod_i (1 + x^{p^i})^{n_i} \pmod p$$ 比较 $x^m$ 系数，$m$的$p$进制表示$m = \sum m_i p^i$唯一对应$\prod \binom{n_i}{m_i}$。

Lucas 推论 1

$\binom{n}{m} \equiv 0 \pmod p$当且仅当存在某$i$使$m_i > n_i$（$p$进制某位$m$大于$n$）。

Lucas 推论 2（奇偶性）

$\binom{n}{m}$为奇数$\iff$ $m$的二进制位均为$n$的对应位的子集，即$m \& n = m$（按位与）。

Lucas 定理应用

求 $\binom{100}{50} \bmod 7$。

解：将 $100, 50$转为$7$ 进制：

  • $100 = 2 \cdot 49 + 0 \cdot 7 + 2 = (202)_7$
  • $50 = 1 \cdot 49 + 0 \cdot 7 + 1 = (101)_7$

Lucas：$\binom{100}{50} \equiv \binom{2}{1} \binom{0}{0} \binom{2}{1} = 2 \cdot 1 \cdot 2 = 4 \pmod 7$。

2.2 广义 Lucas 定理（Andrews） ​

Babbage / Wythoff / Granville 推广

Granville 给出 $\binom{n}{m} \bmod p^q$的公式，基于$p^q$周期下的广义 Wilson 定理。形式较复杂，常用于$p^2$或$p^3$ 模下的二项式计算。

$\binom{n}{m} \bmod p^2$ 公式（Granville）

设 $n, m$的$p$进制展开同前。记$e = v_p\negthinspace\binom{n}{m}$（由 Kummer 给出）。若 $e = 0$： $$\binom{n}{m} \equiv (-1)^{e_0} \prod_{i=0}^{r} \frac{(n_i!)_p}{(m_i!)_p ((n_i-m_i)!)_p} \pmod{p^2}$$ 其中 $(n!)_p = \prod_{\substack{1 \le k \le n \newline p \nmid k}} k$，$e_0$ 为某修正项（详细见 Granville 1997）。

三、Lucas 序列与递推数列 ​

3.1 Lucas 序列 ​

Lucas 序列 $U_n, V_n$

给定整数 $P, Q$，$D = P^2 - 4Q \neq 0$，定义： $$U_0 = 0,\ U_1 = 1,\ U_{n+2} = P U_{n+1} - Q U_n$$ $$V_0 = 2,\ V_1 = P,\ V_{n+2} = P V_{n+1} - Q V_n$$

显式公式（Binet 型）：设 $\alpha, \beta$为$x^2 - Px + Q = 0$ 的两根（$\alpha + \beta = P$，$\alpha\beta = Q$），则 $$U_n = \frac{\alpha^n - \beta^n}{\alpha - \beta},\quad V_n = \alpha^n + \beta^n$$

典型例子：

  • Fibonacci：$P = 1, Q = -1$，$U_n = F_n$，$V_n = L_n$（Lucas 数）
  • Pell：$P = 2, Q = -1$，$U_n$ 为 Pell 数
  • Mersenne 类：$P = 3, Q = 2$，$U_n = 2^n - 1$

3.2 整除性与周期性 ​

Lucas 序列基本性质

  1. 乘性：$U_{mn} = U_m \cdot U_n \cdot(\ldots)$（具体形式复杂）
  2. $\gcd$ 性质：$\gcd(U_m, U_n) = U_{\gcd(m, n)}$（当 $\gcd(P, Q) = 1$）
  3. 整除：$m \mid n \Rightarrow U_m \mid U_n$
  4. 周期：模任意 $m$，$\lbrace U_n\rbrace $ 周期有限（Pisano 周期）

Fibonacci 整除性

$F_m \mid F_n \iff m \mid n$。例：$F_3 = 2 \mid F_6 = 8, F_9 = 34$ ✓；$F_4 = 3 \nmid F_5 = 5$。

3.3 Fibonacci 与 Lucas 恒等式 ​

Fibonacci 经典恒等式

  • $F_{n+1} F_{n-1} - F_n^2 = (-1)^n$（Cassini 恒等式）
  • $F_{m+n} = F_m F_{n+1} + F_{m-1} F_n$
  • $\gcd(F_m, F_n) = F_{\gcd(m,n)}$
  • $F_1 + F_2 + \cdots + F_n = F_{n+2} - 1$
  • $F_1^2 + F_2^2 + \cdots + F_n^2 = F_n F_{n+1}$
  • $F_{2n} = F_n L_n$，$F_{2n+1} = F_{n+1}^2 + F_n^2$

Zeckendorf 表示

每个正整数可唯一表示为不相邻 Fibonacci 数之和： $$n = F_{i_1} + F_{i_2} + \cdots + F_{i_k},\quad i_{j+1} \le i_j - 2$$ 这是 Fibonacci 数系的核心性质，在组合数论与编码中有重要应用。

3.4 Fibonacci 模 $p$ 与 Pisano 周期 ​

Pisano 周期 $\pi(p)$

对素数 $p$，Fibonacci 序列模 $p$的最小正周期$\pi(p)$ 满足：

  • $p \equiv \pm 1 \pmod 5$：$\pi(p) \mid p - 1$
  • $p \equiv \pm 2 \pmod 5$：$\pi(p) \mid 2(p+1)$
  • $p = 5$：$\pi(5) = 20$
  • $p = 2$：$\pi(2) = 3$；$p = 3$：$\pi(3) = 8$

与二次剩余的联系

$\sqrt{5}$在$\mathbb{F}_p$中存在$\iff$ $p \equiv \pm 1 \pmod 5$（即 $5$是模$p$的二次剩余）。这决定 Fibonacci 模$p$ 行为的本质。

四、Catalan 数的整除性 ​

4.1 Catalan 数定义 ​

$$C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)! n!}$$

Catalan 整除性（Kummer）

$v_p(C_n) = v_p\negthinspace\binom{2n}{n} - v_p(n+1)$。由 Kummer 定理，$v_p\negthinspace\binom{2n}{n}$等于$n + n$在$p$ 进制下的进位次数。故 $$v_p(C_n) = (\text{$n+n$在$p$ 进制下的进位次数}) - v_p(n+1)$$

Catalan 素性质（Kaplansky）

$C_n$为奇数$\iff$ $n = 2^k - 1$（$k \ge 0$）。

证明：$C_n$奇$\iff$ $v_2(C_n) = 0$ $\iff$ $n + n$在二进制下无进位且$v_2(n+1) = 0$。前者要求 $n$的二进制无连续$1$，后者要求 $n$ 偶。但更精细地：$n + n$无进位要求每位都是$0$（因 $1+1 = 10$有进位），即$n = 0$？这与 $n = 2^k - 1$ 矛盾。

实际结论是：$C_n$奇$\iff$ $n = 2^k - 1$。这由更细的 Lucas 分析得到。

Catalan 奇偶性

$C_1 = 1$（奇），$C_3 = 5$（奇），$C_7 = 429$（奇），$C_{15} = 9694845$（奇），$C_{31} = \ldots$（奇）。对应 $n = 2^k - 1$。

4.2 Catalan 模 $p$ 的渐近行为 ​

Catalan 模 $p$ 零项比例

对素数 $p$，使得 $C_n \not\equiv 0 \pmod p$的$n \le N$的个数渐近为$N^{\log_p 2 / (1 + \log_p 2)} \cdot N^{o(1)}$（Northshield 2011 等结果）。

五、Stirling 数与分拆数 ​

5.1 Stirling 数 ​

Stirling 数定义

  • 第一类 $s(n, k)$（带符号）：$x^{\underline{n}} = \sum_k s(n,k) x^k$（下降阶乘展开）
  • 第二类 $S(n, k)$（无符号）：$x^n = \sum_k S(n,k) x^{\underline{k}}$

递推： $$S(n+1, k) = k S(n, k) + S(n, k-1)$$

数论性质：

  • $S(n, k) \equiv 0 \pmod{k!}$? 不成立，但 $k! \cdot S(n, k) = $把$n$元集分到$k$ 个非空盒的方式数
  • $S(p, k) \equiv 0 \pmod{p}$当$2 \le k \le p - 1$（用 $p$ 元循环群作用）

$S(p, k) \bmod p$

$S(p, k)$模$p$仅在$k = 1, 2, p$ 处非零。$S(p, 1) = 1, S(p, 2) = 2^{p-1} - 1 \equiv 1 \pmod p$（Fermat 小定理）, $S(p, p) = 1$。

5.2 分拆数 $p(n)$ ​

分拆数

$p(n)$是将$n$ 写成正整数之和（不计顺序）的方式数。

生成函数： $$\sum_{n=0}^{\infty} p(n) x^n = \prod_{k=1}^{\infty} \frac{1}{1 - x^k}$$

Hardy-Ramanujan 渐近公式： $$p(n) \sim \frac{1}{4n\sqrt{3}} \exp\negthinspace\left(\pi \sqrt{\frac{2n}{3}}\right) \quad (n \to \infty)$$

Ramanujan 同余式

$$p(5n+4) \equiv 0 \pmod 5$$ $$p(7n+5) \equiv 0 \pmod 7$$ $$p(11n+6) \equiv 0 \pmod{11}$$

Atkin（1968）证明了对任意与 $24$互素的$m$，存在模 $m$ 的 Ramanujan 型同余。

验证 Ramanujan 同余

$p(4) = 5 \equiv 0 \pmod 5$ ✓（$4 = 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1$ 共 5 种） $p(5) = 7 \equiv 0 \pmod 7$ ✓ $p(6) = 11 \equiv 0 \pmod{11}$ ✓

六、典型二项式恒等式的数论意义 ​

6.1 Vandermonde 恒等式 ​

$$\binom{m+n}{k} = \sum_{j=0}^{k} \binom{m}{j}\binom{n}{k-j}$$

模 $p$形式：若$m = p a + m_0$, $n = p b + n_0$, $k = p c + k_0$（$p$ 进制首位），则 $$\binom{m+n}{k} \equiv \binom{a+b}{c} \binom{m_0+n_0}{k_0} \pmod p$$ 这是 Lucas 定理的另一种证明思路。

6.2 二项式定理模 $p$ ​

Freshman's Dream

在 $\mathbb{F}_p[x]$ 中： $$(1 + x)^p \equiv 1 + x^p \pmod p$$ 更一般地，$(a + b)^p \equiv a^p + b^p \pmod p$。

这是 Frobenius 自同态的核心，是 Lucas 定理的代数基础。

6.3 Chu-Vandermonde 恒等式 ​

$$\sum_{k=0}^{n} \binom{r}{k}\binom{s}{n-k} = \binom{r+s}{n}$$

模 $p$ 下与 Lucas 定理结合可解大量竞赛题。

七、竞赛典型例题 ​

例 1：求奇数二项式系数个数

对 $n = 100$，$\binom{100}{k}$ 中有多少个奇数？

解：$\binom{100}{k}$奇$\iff$ $k \& 100 = k$（按位与）。$100 = 1100100_2$。 $k$的取法：每位独立选$0$或对应$1$。设 $1$的位数为$s_2(100) = 3$，则 $k$的个数为$2^3 = 8$。

验证：$k \in \lbrace 0, 4, 32, 36, 64, 68, 96, 100\rbrace $。

例 2：求 $\binom{2p}{p} \bmod p^3$（Wolstenholme 型）

对素数 $p \ge 5$，证明 $\binom{2p}{p} \equiv 2 \pmod{p^3}$（Wolstenholme 定理）。

证：$\binom{2p}{p} = \dfrac{(2p)!}{(p!)^2} = \dfrac{(p+1)(p+2)\cdots(2p)}{p!} = \dfrac{p \cdot (p+1)(p+2)\cdots(2p-1)}{p!} \cdot 2 = 2 \prod_{k=1}^{p-1} \dfrac{p+k}{k}$。

$$\binom{2p}{p} = 2 \prod_{k=1}^{p-1} \left(1 + \frac{p}{k}\right) = 2 \left(1 + p \sum \frac{1}{k} + p^2 \sum_{j<k} \frac{1}{jk} + \cdots\right)$$

由 Wolstenholme 引理：$\sum_{k=1}^{p-1} \dfrac{1}{k} \equiv 0 \pmod{p^2}$（$p \ge 5$），$\sum_{j<k} \dfrac{1}{jk} \equiv 0 \pmod{p}$。故 $$\binom{2p}{p} \equiv 2(1 + 0 + 0) = 2 \pmod{p^3}$$

详见 整除与同余基础 中 Wolstenholme 定理。

例 3：Lucas 定理求和

计算 $\sum_{k=0}^{n} \binom{n}{k} \bmod p$，其中 $n = p^r - 1$。

解：$n$的$p$进制每位都是$p-1$。由 Lucas，$\binom{n}{k} \equiv \prod \binom{p-1}{k_i}$。每个 $k_i \in [0, p-1]$ 独立取值，$\binom{p-1}{k_i} \equiv (-1)^{k_i} \pmod p$。 $$\sum_{k=0}^{n} \binom{n}{k} \equiv \prod_{i=0}^{r-1} \sum_{k_i=0}^{p-1} (-1)^{k_i} = \prod_{i=0}^{r-1} 0 = 0 \pmod p$$ 但等等：$\sum_{k=0}^{p-1} (-1)^{k_i} = 1 - 1 + 1 - \cdots + (-1)^{p-1}$。对奇 $p$，$(-1)^{p-1} = 1$，奇偶数项各 $(p-1)/2$与$(p+1)/2$个，和为$0$。✓

故 $\sum_{k=0}^{n} \binom{n}{k} \equiv 0 \pmod p$（与 $\sum = 2^n \equiv 2^{p^r - 1} = (2^{p-1})^{(p^r-1)/(p-1)} \equiv 1$? 矛盾，需重新检查）。

重新：$\sum \binom{n}{k} = 2^n$，$n = p^r - 1$。$2^{p^r - 1} \bmod p$：由 Fermat，$2^{p-1} \equiv 1$，$p^r - 1 = (p-1)(p^{r-1} + \cdots + 1)$，故 $2^{p^r - 1} \equiv 1 \pmod p$。

Lucas 推导错在 $\sum_{k_i=0}^{p-1}(-1)^{k_i}$：当 $p$奇时$= 0$，但 $\prod 0 = 0 \ne 1$。问题在于 $k = n$时所有$k_i = p-1$，$\prod (-1)^{p-1} = 1$（贡献 $+1$）。但其它 $k$各贡献$0$。故 $\sum = 0 + 1 = 1$ ✓。

正确答案：$\sum_{k=0}^{n} \binom{n}{k} \equiv 1 \pmod p$，对应 $2^n \equiv 1$。

例 4：分拆数 $p(24)$ 的整除

用 Ramanujan 同余判定 $p(24)$ 的整除性。

解：$24 = 5 \cdot 4 + 4 \Rightarrow p(24) \equiv 0 \pmod 5$。 $24 = 7 \cdot 3 + 3$，但 $5 = 7 \cdot 0 + 5$，$24 \ne 7n + 5$。 $24 = 11 \cdot 2 + 2$，$24 \ne 11n + 6$。 故仅保证 $5 \mid p(24)$。查表 $p(24) = 1575 = 5^2 \cdot 63 = 5^2 \cdot 9 \cdot 7$，确实 $5 \mid p(24)$，且 $7 \mid p(24)$。

例 5：Fibonacci 模 7

求 Fibonacci 数列模 $7$ 的周期。

解：$7 \equiv 2 \pmod 5$，$\pi(7) \mid 2 \cdot 8 = 16$。计算 $F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8 \equiv 1, F_7 = 13 \equiv 6, F_8 = 21 \equiv 0, F_9 = 34 \equiv 6, F_{10} = 55 \equiv 6, F_{11} = 89 \equiv 5, F_{12} = 144 \equiv 4, F_{13} = 233 \equiv 2, F_{14} = 377 \equiv 6, F_{15} = 610 \equiv 1, F_{16} = 987 \equiv 0, F_{17} = 1597 \equiv 1, F_{18} = 2584 \equiv 1$。

$F_{17} \equiv F_1, F_{18} \equiv F_2$，周期 $\pi(7) = 16$。

例 6：Lucas 数模 $p$ 与原根

设 $p \equiv \pm 1 \pmod 5$，证明 $F_{p-1} \equiv 0 \pmod p$。

证：$\pi(p) \mid p - 1$，故 $F_{p-1} \equiv F_0 = 0 \pmod p$。

例：$p = 11 \equiv 1 \pmod 5$，$F_{10} = 55 = 5 \cdot 11$，确实 $11 \mid F_{10}$。

例 7：Stirling 数模 $p$

证明 $S(p+1, k) \equiv 1 + \binom{p}{k-1} \pmod p$，并求 $k \in \lbrace 2, 3, p\rbrace $ 时的值。

解：递推 $S(p+1, k) = k S(p, k) + S(p, k-1)$。已知 $S(p, k) \equiv 0$（$2 \le k \le p-1$），$S(p, 1) = S(p, p) = 1$。

  • $k = 2$：$S(p+1, 2) = 2 \cdot 0 + S(p, 1) = 1 \pmod p$
  • $k = 3$：$S(p+1, 3) = 3 \cdot 0 + 0 = 0 \pmod p$（$p \ge 5$）
  • $k = p$：$S(p+1, p) = p \cdot S(p, p) + S(p, p-1) = p \cdot 1 + 0 = 0 \pmod p$? 但 $S(p, p-1) = \binom{p}{2}$，$\binom{p}{2} = p(p-1)/2 \equiv 0 \pmod p$。故 $S(p+1, p) \equiv 0 + 0 = 0$? 不对，$S(p+1, p) = \binom{p+1}{2}$（将 $p+1$元分到$p$ 盒，恰一盒两元素），$= p(p+1)/2 \equiv 0 \pmod p$ ✓。

例 8：Kummer 求高次整除

求 $v_3\negthinspace\binom{3^n}{3^{n-1}}$。

解：$3^n$在$3$进制为$1\underbrace{00\ldots0}_{n}$（$1$后跟$n$个$0$）。$3^{n-1}$为$1$后跟$n-1$个$0$。

加法 $3^{n-1} + (3^n - 3^{n-1}) = 3^{n-1} + 2 \cdot 3^{n-1} = 3^n$。在 $3$ 进制下：

  • $3^{n-1} = 100\ldots0_3$（$1$后$n-1$个$0$）
  • $3^n - 3^{n-1} = 2 \cdot 3^{n-1} = 200\ldots0_3$
  • 加和：每位独立，无进位

故 $v_3\negthinspace\binom{3^n}{3^{n-1}} = 0$。验证：$\binom{9}{3} = 84 = 4 \cdot 3 \cdot 7$，$v_3 = 1$？与计算不符。重算：$\binom{3^n}{3^{n-1}}$中$m = 3^{n-1}$，$n - m = 3^n - 3^{n-1} = 2 \cdot 3^{n-1}$。$3^{n-1} + 2 \cdot 3^{n-1}$在$3$进制：第$n-1$位$1 + 2 = 3$，进位到第 $n$位。共$1$次进位。故$v_3 = 1$✓。修正前面的分析：第$n-1$ 位确实进位。

八、与更高深数论的联系 ​

8.1 $p$-adic Gamma 函数与 Morita ​

$p$-adic Gamma 函数 $\Gamma_p$是经典$\Gamma$在$\mathbb{Z}_p$上的推广，与$\binom{n}{m} \bmod p^k$的精细计算紧密相关。Granville 定理用$\Gamma_p$给出二项式系数模$p^q$ 的精确公式。

8.2 组合恒等式与超几何级数 ​

许多组合恒等式（如 Chu-Vandermonde、Dixon、Whipple）是超几何级数 $_pF_q$ 的特殊情形，与模形式、椭圆曲线的周期积分有深层联系。

8.3 Catalan 数与代数几何 ​

Catalan 数 $C_n$计数$\mathbb{P}^2$上度$n$有理曲线的 Gromov-Witten 不变量（Kontsevich）。分拆数$p(n)$与 Dedekind$\eta$ 函数相关： $$\eta(\tau) = q^{1/24} \prod_{n=1}^{\infty} (1 - q^n),\quad q = e^{2\pi i \tau}$$

九、竞赛考点速查 ​

定理核心结论竞赛层次
Lucas 定理$\binom{n}{m} \bmod p$化为$p$ 进制逐位一试/二试
Kummer 定理$v_p\negthinspace\binom{n}{m}$ = 进位次数二试/TST
Wolstenholme$\binom{2p}{p} \equiv 2 \pmod{p^3}$TST/CMO
Granville$\binom{n}{m} \bmod p^q$高级
Cassini$F_{n+1}F_{n-1} - F_n^2 = (-1)^n$一试/二试
$\gcd(F_m, F_n) = F_{\gcd}$Fibonacci 整除性二试
Pisano 周期Fibonacci 模 $m$ 周期TST
Ramanujan 同余$p(5n+4) \equiv 0 \pmod 5$TST/CMO
Catalan 奇偶$C_n$奇$\iff$ $n = 2^k - 1$TST
Stirling 模 $p$$S(p, k) \equiv 0$（$2 \le k \le p-1$）二试

十、知识链接 ​

十一、mermaid 图：核心定理关系 ​

mermaid
graph TD
    A[二项式系数 n choose m]
    A --> B[Lucas 定理: 模 p 计算]
    A --> C[Kummer 定理: v_p 计算]
    A --> D[Legendre 公式: v_p n!]
    
    B --> E[Freshman's Dream: 1+x^p = 1+x)^p mod p]
    B --> F[奇偶性: n&m=m]
    
    C --> G[进位次数 = v_p]
    C --> H[和公式 s_p n + s_p m - s_p]
    
    D --> I[v_p binom = v_p n! - v_p m! - v_p n-m!]
    I --> C
    
    E --> J[Frobenius 自同态]
    J --> K[有限域 F_p^a]
    
    A --> L[Catalan 数 C_n = 1/n+1 binom 2n n]
    L --> M[Kaplansky 奇偶定理]
    
    A --> N[Stirling 数]
    N --> O[S p, k mod p]
    
    P[Lucas 序列 U_n, V_n]
    P --> Q[Fibonacci F_n]
    P --> R[Lucas 数 L_n]
    Q --> S[Cassini 恒等式]
    Q --> T[gcd F_m, F_n = F_gcd]
    Q --> U[Pisano 周期]
    U --> V[依赖 5/p 二次剩余]

十二、附录：常用 $p$-adic 数据 ​

$p$$v_p(p!)$$v_p((p^2)!)$$\pi(p)$Pisano$\pi(p^2)$
$2$$1$$3$$3$$6$
$3$$1$$4$$8$$24$
$5$$1$$6$$20$$100$
$7$$1$$8$$16$$112$
$11$$1$$12$$10$$110$
$13$$1$$14$$28$$364$

% 注：Pisano 周期 $\pi(p^2) = p \cdot \pi(p)$在大多数情况下成立（Wall 猜想：除$p = 2, 5$ 外无反例）。

基于 Obsidian 整理 · 由 VitePress 构建

学习笔记