Skip to content

查看源代码:
lucas-theorem-story-proof.md

---
title: 当初没有人认为它能走到这里——Lucas 定理的讲故事法证明
createTime: 2026/11/17
categories:
  - study
tags:
  - maths
  - study-note
  - AI-powered
---

依旧人类推导,AI 编写。AI 太好用了你们知道吗,还能生成插图。

关于 Lucas 定理,我们脑子里蹦出来的第一个画面往往是 Freshman's dream:$(1+x)^p \equiv 1 + x^p$,然后一堆多项式在 $\mathbb{F}_p$ 上互相抵消。

这个画面很有效,但也很冷——没有一个人,没有一件东西,没有一个能用手指着说“就这里”的场景。

“讲故事法”大概是最晚被想出来的那条路:把定理翻译成一个看得见的组合情境,让结论自己从场景里浮出来,而不是我们伸手去把它推出来。当初没有人认为它能走到这里——1878 年写下这个同余式的 Édouard Lucas 手边没有那张桌子,也没有那个轮子。

后来它确实走到了。而且这条路有意思的地方在于:它把“为什么偏偏是逐位相乘”这件事,说成了人话。

这篇博客就带你走这条路。**一张方阵、一圈轮子、和一堆拧不动的选法。**

## 定理

:::theorem Lucas 定理
设 $p$ 为素数,$n, k$ 为非负整数。把 $n, k$ 写成 $p$ 进制:

$$ n = n_0 + n_1 p + n_2 p^2 + \cdots + n_s p^s, \qquad k = k_0 + k_1 p + k_2 p^2 + \cdots + k_s p^s $$

其中 $0 \le n_i, k_i < p$。则

$$ \mathrm{C}_n^k \equiv \prod_{i=0}^{s} \mathrm{C}_{n_i}^{k_i} \pmod{p} $$

约定 $b > a$ 时 $\mathrm{C}_a^b = 0$。
:::

## 先看一眼它长什么样

举一个例子:$p = 3$,$n = 8$,$k = 4$。$8 = (22)_3$,$4 = (11)_3$,于是

$$ \mathrm{C}_8^4 \equiv \mathrm{C}_2^1 \cdot \mathrm{C}_2^1 = 4 \equiv 1 \pmod 3. $$

而 $\mathrm{C}_8^4 = 70 = 69 + 1$,确实模 $3$ 余 $1$。

这条规律的意思是:**$n$ 和 $k$ 的 $p$ 进制每一位可以各算各的,算完再乘起来**,位与位之间彻底断联了。

## 常规证法长什么样

三十秒版本:在 $\mathbb{F}_p$ 上有 $(1+x)^p \equiv 1 + x^p$,于是把 $n$ 写成 $n = pm + r$,得

$$ (1+x)^n = \bigl((1+x)^p\bigr)^m (1+x)^r \equiv (1+x^p)^m (1+x)^r \pmod{p}, $$

再比较 $x^k$ 的系数,Lucas 定理就出来了。

干净利落,但从头到尾没有一个画面,全是多项式在自说自话。

所以下面换一个路子:**造一张桌子、一个轮子出来**。

## 讲故事法证明

### 第一幕:剖开 n 个元素

设 $n = pm + r$,其中 $m = \lfloor n/p \rfloor$,$0 \le r < p$。

现在我们手上有 $n$ 个元素——就当是 $n$ 个一模一样的球吧。把它们摆成一张 $m$ 行 $p$ 列的方阵:每列 $\lfloor n/p \rfloor$ 个,正好占满 $m$ 行;剩下的 $r = n - pm = n \bmod p$ 个元素单独搁在旁边当“零头”。

:::center
![剖分与轮换](./lucas-theorem-story-proof/image.svg){width=660px}
:::

要问的问题是:**从这 $n$ 个元素里挑 $k$ 个,一共有多少种挑法?**

答案当然是 $\mathrm{C}_n^k$。但我们不打算正面去数,我们要绕一圈。

顺带一提,列的顺序其实无关紧要,我们只是把它们排成一排方便看。

### 第二幕:拧一圈

把这 $p$ 列首尾相接,接成一个圆环。然后拧一格:第 $i$ 列整体挪到第 $i+1$ 列(最后一列绕回第一列),**行号保持不变**,零头原地不动。

这是一个 $\mathbb{Z}_p$ 的作用,作用在“所有 $k$ 元选法”组成的集合上。

这个把戏有三个要点:

1. $p$ 是素数,所以每个轨道的大小只能是 $1$ 或者 $p$。也就是说,所有选法被分成一堆一堆:绝大多数一堆 $p$ 个,剩下的每堆只有 $1$ 个(拧了也不动)。
2. 因为拧的时候行号不动,所以**每一行的 $p$ 个格子恰好是一个轨道**。
3. 零头是 $r$ 个各自为营的单点轨道。

于是我们只要数清楚“拧了也不动”的选法有几个,剩下的全都是 $p$ 的倍数,对 $p$ 取模时直接归零。

这就是群作用那一套的标准套路:用**不动点**去数总数模 $p$ 的余数。

### 第三幕:数拧不动的选法

一个选法拧了之后不变,意味着:**它要么整行地要,要么整行地不要。**

为什么?假如第 $j$ 行的某一格被选上了,那么拧一格之后同一行的下一格也必须被选上(不然这个选法就变了),再拧下去,这一整行 $p$ 格全被选上。反过来,整行全选或整行不选,确实拧了也不动。

所以拧不动的选法 = 若干整行 + 随便挑几个零头。

设挑了 $j$ 整行、$t$ 个零头,那么

$$ pj + t = k, \qquad 0 \le t \le r < p. $$

左边对 $p$ 取模得到 $t \equiv k \pmod p$,而 $0 \le t < p$,所以 **$t$ 只能是 $k$ 的最低位** $k_0 = k \bmod p$,进而 $j = \lfloor k/p \rfloor$。

换句话说,$t$ 一点自由选择的余地都没有——这不是巧合,而是 $k$ 自己的 $p$ 进制在说话。

于是拧不动的选法一共有

$$ \mathrm{C}_m^{\lfloor k/p \rfloor} \cdot \mathrm{C}_r^{k_0} $$

个:从前 $m$ 行里挑 $\lfloor k/p \rfloor$ 行出来,从 $r$ 个零头里挑 $k_0$ 个。

(若 $k_0 > r$,零头一个都凑不齐,按开头的约定这一项就是 $0$——整个选法直接归零,也对。)

其余选法每 $p$ 个凑一堆,于是

$$ \mathrm{C}_n^k \equiv \mathrm{C}_m^{\lfloor k/p \rfloor} \cdot \mathrm{C}_r^{k_0} \pmod p. $$

:::note 这一步是全篇的心脏
“拧不动”把 $k$ 的 $p$ 进制最低位 $k_0$ 单独摘了出来,剩下的 $\lfloor k/p \rfloor$ 原封不动地留给下一幕——正好是 Lucas 定理该有的样子。
:::

### 第四幕:递归与归纳

:::lemma 递推式
设 $p$ 为素数,$n = pm + r$($0 \le r < p$),$k_0 = k \bmod p$,则

$$ \mathrm{C}_n^k \equiv \mathrm{C}_m^{\lfloor k/p \rfloor} \cdot \mathrm{C}_r^{k_0} \pmod p. $$
:::

现在把式子里的三个数翻译成 $p$ 进制:

- $r = n - pm = n \bmod p$,正好是 $n$ 的最低位 $n_0$;
- $k_0 = k \bmod p$,是 $k$ 的最低位;
- $m = \lfloor n/p \rfloor$ 相当于把 $n$ 的 $p$ 进制右移一位,它的各位是 $n_1, n_2, \dots$;
- $\lfloor k/p \rfloor$ 同样右移一位,各位是 $k_1, k_2, \dots$。

所以递推式其实是

$$ \mathrm{C}_n^k \equiv \mathrm{C}_{n_0}^{k_0} \cdot \mathrm{C}_{\lfloor n/p \rfloor}^{\lfloor k/p \rfloor} \pmod p. $$

右边第二项的参数 $\lfloor n/p \rfloor$ 严格小于 $n$,于是可以对外层的 $n$ 做归纳。设结论对一切小于 $n$ 的上标成立,则

$$ \mathrm{C}_{\lfloor n/p \rfloor}^{\lfloor k/p \rfloor} \equiv \prod_{i \ge 1} \mathrm{C}_{n_i}^{k_i} \pmod p. $$

两式一乘,Lucas 定理就掉了出来。

归纳基取 $n = 0$:$\mathrm{C}_0^k$ 只有 $k = 0$ 时非零,而乘积 $\prod_{i \ge 0} \mathrm{C}_{0}^{k_i}$ 在 $k = 0$ 时为 $1$、在 $k > 0$ 时为 $0$,两边对得上。

$$ \boxed{\mathrm{C}_n^k \equiv \prod_{i=0}^{s} \mathrm{C}_{n_i}^{k_i} \pmod p} $$

:::right
$\square$
:::

## 故事讲完了,能带走什么

### 推论一:什么时候被 p 整除

由定理立刻得到:$\mathrm{C}_n^k \equiv 0 \pmod p$ 当且仅当存在某一位 $k_i > n_i$。

用 $p$ 进制减法的话说,这就是**$k - n$ 在 $p$ 进制上要借位**。

比如 $p = 2$,$n = 13 = (1101)_2$:$k = 5 = (0101)_2$ 时一位都不缺,$\mathrm{C}_{13}^5 = 1287$ 是奇数;$k = 6 = (0110)_2$ 时第三位不够,得向高位借位,$\mathrm{C}_{13}^6 = 1716$ 就是偶数。

这也是 OI 里判零的标准套路:先把 $n, k$ 拆成 $p$ 进制,某一位不够就直接输出 $0$。

### 推论二:Freshman's dream 也有画面

$(1+x)^p \equiv 1 + x^p$ 的组合版本,用的其实是同一招:在 $p$ 个位置各填 $0$ 或 $1$,拧动这 $p$ 个位置构成循环群,轨道大小 $1$ 或 $p$,而不动点只有“全 $0$”和“全 $1$”两种。

所以 $0 < k < p$ 时,$\mathrm{C}_p^k$ 一定是 $p$ 的倍数,只有两个端点活了下来——这正是 Freshman's dream。

同一套工具,把“拧一格”用在 $m$ 行 $p$ 列的方阵上,每一行也是一个轨道——这正是上面那个故事。

### 推论三:这个定理后来走到了哪里

- **数字组合学**:Granville 1997 年的《Binomial coefficients mod a prime power》把模 $p$ 的结论推进到模 $p^k$,中间夹着一层 $p$-进赋值。
- **OI**:卢卡斯定理成了模板题(P3807),求 $\mathrm{C}_n^k \bmod p$ 时逐位算再相乘,比直接算组合数快得多。
- **另一条线**:群表示论里还有个同名的 Frobenius–Lucas 定理,讲的是 $p$-群不可约特征标的个数。和本文这条线没什么关系,但也都姓 Lucas。

顺便说一句,Lucas 更出名的其实是他的 Lucas 数列。定理和数列只共享一个人的姓氏,这大概是数学里最省事的跨界方式之一。

## 把故事写进程序

:::details Code
```python
from math import comb


def lucas(n: int, k: int, p: int) -> int:
    """Lucas 定理:逐位做组合数再相乘。"""
    ans = 1
    while n or k:
        ni, ki = n % p, k % p
        if ki > ni:
            return 0
        ans = ans * comb(ni, ki) % p
        n //= p
        k //= p
    return ans


# 自检:和精确值逐个对拍
for p in (2, 3, 5, 7):
    for n in range(0, 40):
        for k in range(0, n + 1):
            assert lucas(n, k, p) == comb(n, k) % p
print("all good")
```
:::

## 结语

回头看,这个证明里最关键的一步,其实只是把“选 $k$ 个”换成了“在群作用下数不动点”。凡是碰到模素数的组合计数,这一招几乎总是第一反应。

不过当年 Lucas 写下这个式子的时候,大概想不到有人能为它编出这样一个故事。他只是顺手记下一个规律,然后转身去研究别的去了。一百多年后我们把它讲成了故事——某种意义上,是我们自己在替它续命。

当然,这个故事谈不上独创:群作用、轨道计数、不动点,Burnside 那一套工具人尽皆知。难的从来不是工具,而是把它摆成一张桌子、一个轮子,让“为什么偏偏是逐位相乘”这件事显形出来。

改天写篇群表示论里那个 Frobenius–Lucas 定理,那才是真正的重头戏。*

:::warning *
刚刚那个“改天写”是 AI 自己写的。

不排除人类鸽掉这个的可能。
:::