Skip to content

当初没有人认为它能走到这里——Lucas 定理的讲故事法证明

约 2603 字大约 9 分钟

mathsstudy-noteAI-powered

2026-11-17

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

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

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

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

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

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

定理

Lucas 定理

设 pp 为素数,n,kn, k 为非负整数。把 n,kn, k 写成 pp 进制:

n=n0+n1p+n2p2+⋯+nsps,k=k0+k1p+k2p2+⋯+ksps 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≤ni,ki<p0 \le n_i, k_i < p。则

Cnk≡∏i=0sCniki(modp) \mathrm{C}_n^k \equiv \prod_{i=0}^{s} \mathrm{C}_{n_i}^{k_i} \pmod{p}

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

先看一眼它长什么样

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

C84≡C21⋅C21=4≡1(mod3). \mathrm{C}_8^4 \equiv \mathrm{C}_2^1 \cdot \mathrm{C}_2^1 = 4 \equiv 1 \pmod 3.

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

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

常规证法长什么样

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

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

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

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

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

讲故事法证明

第一幕:剖开 n 个元素

设 n=pm+rn = pm + r,其中 m=⌊n/p⌋m = \lfloor n/p \rfloor,0≤r<p0 \le r < p。

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

剖分与轮换

要问的问题是:从这 nn 个元素里挑 kk 个,一共有多少种挑法?

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

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

第二幕:拧一圈

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

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

这个把戏有三个要点:

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

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

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

第三幕:数拧不动的选法

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

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

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

设挑了 jj 整行、tt 个零头,那么

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

左边对 pp 取模得到 t≡k(modp)t \equiv k \pmod p,而 0≤t<p0 \le t < p,所以 tt 只能是 kk 的最低位 k0=k mod pk_0 = k \bmod p,进而 j=⌊k/p⌋j = \lfloor k/p \rfloor。

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

于是拧不动的选法一共有

Cm⌊k/p⌋⋅Crk0 \mathrm{C}_m^{\lfloor k/p \rfloor} \cdot \mathrm{C}_r^{k_0}

个:从前 mm 行里挑 ⌊k/p⌋\lfloor k/p \rfloor 行出来,从 rr 个零头里挑 k0k_0 个。

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

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

Cnk≡Cm⌊k/p⌋⋅Crk0(modp). \mathrm{C}_n^k \equiv \mathrm{C}_m^{\lfloor k/p \rfloor} \cdot \mathrm{C}_r^{k_0} \pmod p.

这一步是全篇的心脏

“拧不动”把 kk 的 pp 进制最低位 k0k_0 单独摘了出来,剩下的 ⌊k/p⌋\lfloor k/p \rfloor 原封不动地留给下一幕——正好是 Lucas 定理该有的样子。

第四幕:递归与归纳

递推式

设 pp 为素数,n=pm+rn = pm + r(0≤r<p0 \le r < p),k0=k mod pk_0 = k \bmod p,则

Cnk≡Cm⌊k/p⌋⋅Crk0(modp). \mathrm{C}_n^k \equiv \mathrm{C}_m^{\lfloor k/p \rfloor} \cdot \mathrm{C}_r^{k_0} \pmod p.

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

  • r=n−pm=n mod pr = n - pm = n \bmod p,正好是 nn 的最低位 n0n_0;
  • k0=k mod pk_0 = k \bmod p,是 kk 的最低位;
  • m=⌊n/p⌋m = \lfloor n/p \rfloor 相当于把 nn 的 pp 进制右移一位,它的各位是 n1,n2,…n_1, n_2, \dots;
  • ⌊k/p⌋\lfloor k/p \rfloor 同样右移一位,各位是 k1,k2,…k_1, k_2, \dots。

所以递推式其实是

Cnk≡Cn0k0⋅C⌊n/p⌋⌊k/p⌋(modp). \mathrm{C}_n^k \equiv \mathrm{C}_{n_0}^{k_0} \cdot \mathrm{C}_{\lfloor n/p \rfloor}^{\lfloor k/p \rfloor} \pmod p.

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

C⌊n/p⌋⌊k/p⌋≡∏i≥1Cniki(modp). \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=0n = 0:C0k\mathrm{C}_0^k 只有 k=0k = 0 时非零,而乘积 ∏i≥0C0ki\prod_{i \ge 0} \mathrm{C}_{0}^{k_i} 在 k=0k = 0 时为 11、在 k>0k > 0 时为 00,两边对得上。

Cnk≡∏i=0sCniki(modp) \boxed{\mathrm{C}_n^k \equiv \prod_{i=0}^{s} \mathrm{C}_{n_i}^{k_i} \pmod p}

□\square

故事讲完了,能带走什么

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

由定理立刻得到:Cnk≡0(modp)\mathrm{C}_n^k \equiv 0 \pmod p 当且仅当存在某一位 ki>nik_i > n_i。

用 pp 进制减法的话说,这就是k−nk - n 在 pp 进制上要借位。

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

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

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

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

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

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

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

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

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

把故事写进程序

Code
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")

结语

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

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

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

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

*

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

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