外观
当初没有人认为它能走到这里——Lucas 定理的讲故事法证明
依旧人类推导,AI 编写。AI 太好用了你们知道吗,还能生成插图。
关于 Lucas 定理,我们脑子里蹦出来的第一个画面往往是 Freshman's dream:(1+x)p≡1+xp,然后一堆多项式在 Fp 上互相抵消。
这个画面很有效,但也很冷——没有一个人,没有一件东西,没有一个能用手指着说“就这里”的场景。
“讲故事法”大概是最晚被想出来的那条路:把定理翻译成一个看得见的组合情境,让结论自己从场景里浮出来,而不是我们伸手去把它推出来。当初没有人认为它能走到这里——1878 年写下这个同余式的 Édouard Lucas 手边没有那张桌子,也没有那个轮子。
后来它确实走到了。而且这条路有意思的地方在于:它把“为什么偏偏是逐位相乘”这件事,说成了人话。
这篇博客就带你走这条路。一张方阵、一圈轮子、和一堆拧不动的选法。
定理
Lucas 定理
设 p 为素数,n,k 为非负整数。把 n,k 写成 p 进制:
n=n0+n1p+n2p2+⋯+nsps,k=k0+k1p+k2p2+⋯+ksps
其中 0≤ni,ki<p。则
Cnk≡i=0∏sCniki(modp)
约定 b>a 时 Cab=0。
先看一眼它长什么样
举一个例子:p=3,n=8,k=4。8=(22)3,4=(11)3,于是
C84≡C21⋅C21=4≡1(mod3).
而 C84=70=69+1,确实模 3 余 1。
这条规律的意思是:n 和 k 的 p 进制每一位可以各算各的,算完再乘起来,位与位之间彻底断联了。
常规证法长什么样
三十秒版本:在 Fp 上有 (1+x)p≡1+xp,于是把 n 写成 n=pm+r,得
(1+x)n=((1+x)p)m(1+x)r≡(1+xp)m(1+x)r(modp),
再比较 xk 的系数,Lucas 定理就出来了。
干净利落,但从头到尾没有一个画面,全是多项式在自说自话。
所以下面换一个路子:造一张桌子、一个轮子出来。
讲故事法证明
第一幕:剖开 n 个元素
设 n=pm+r,其中 m=⌊n/p⌋,0≤r<p。
现在我们手上有 n 个元素——就当是 n 个一模一样的球吧。把它们摆成一张 m 行 p 列的方阵:每列 ⌊n/p⌋ 个,正好占满 m 行;剩下的 r=n−pm=nmodp 个元素单独搁在旁边当“零头”。
要问的问题是:从这 n 个元素里挑 k 个,一共有多少种挑法?
答案当然是 Cnk。但我们不打算正面去数,我们要绕一圈。
顺带一提,列的顺序其实无关紧要,我们只是把它们排成一排方便看。
第二幕:拧一圈
把这 p 列首尾相接,接成一个圆环。然后拧一格:第 i 列整体挪到第 i+1 列(最后一列绕回第一列),行号保持不变,零头原地不动。
这是一个 Zp 的作用,作用在“所有 k 元选法”组成的集合上。
这个把戏有三个要点:
- p 是素数,所以每个轨道的大小只能是 1 或者 p。也就是说,所有选法被分成一堆一堆:绝大多数一堆 p 个,剩下的每堆只有 1 个(拧了也不动)。
- 因为拧的时候行号不动,所以每一行的 p 个格子恰好是一个轨道。
- 零头是 r 个各自为营的单点轨道。
于是我们只要数清楚“拧了也不动”的选法有几个,剩下的全都是 p 的倍数,对 p 取模时直接归零。
这就是群作用那一套的标准套路:用不动点去数总数模 p 的余数。
第三幕:数拧不动的选法
一个选法拧了之后不变,意味着:它要么整行地要,要么整行地不要。
为什么?假如第 j 行的某一格被选上了,那么拧一格之后同一行的下一格也必须被选上(不然这个选法就变了),再拧下去,这一整行 p 格全被选上。反过来,整行全选或整行不选,确实拧了也不动。
所以拧不动的选法 = 若干整行 + 随便挑几个零头。
设挑了 j 整行、t 个零头,那么
pj+t=k,0≤t≤r<p.
左边对 p 取模得到 t≡k(modp),而 0≤t<p,所以 t 只能是 k 的最低位 k0=kmodp,进而 j=⌊k/p⌋。
换句话说,t 一点自由选择的余地都没有——这不是巧合,而是 k 自己的 p 进制在说话。
于是拧不动的选法一共有
Cm⌊k/p⌋⋅Crk0
个:从前 m 行里挑 ⌊k/p⌋ 行出来,从 r 个零头里挑 k0 个。
(若 k0>r,零头一个都凑不齐,按开头的约定这一项就是 0——整个选法直接归零,也对。)
其余选法每 p 个凑一堆,于是
Cnk≡Cm⌊k/p⌋⋅Crk0(modp).
这一步是全篇的心脏
“拧不动”把 k 的 p 进制最低位 k0 单独摘了出来,剩下的 ⌊k/p⌋ 原封不动地留给下一幕——正好是 Lucas 定理该有的样子。
第四幕:递归与归纳
递推式
设 p 为素数,n=pm+r(0≤r<p),k0=kmodp,则
Cnk≡Cm⌊k/p⌋⋅Crk0(modp).
现在把式子里的三个数翻译成 p 进制:
- r=n−pm=nmodp,正好是 n 的最低位 n0;
- k0=kmodp,是 k 的最低位;
- m=⌊n/p⌋ 相当于把 n 的 p 进制右移一位,它的各位是 n1,n2,…;
- ⌊k/p⌋ 同样右移一位,各位是 k1,k2,…。
所以递推式其实是
Cnk≡Cn0k0⋅C⌊n/p⌋⌊k/p⌋(modp).
右边第二项的参数 ⌊n/p⌋ 严格小于 n,于是可以对外层的 n 做归纳。设结论对一切小于 n 的上标成立,则
C⌊n/p⌋⌊k/p⌋≡i≥1∏Cniki(modp).
两式一乘,Lucas 定理就掉了出来。
归纳基取 n=0:C0k 只有 k=0 时非零,而乘积 ∏i≥0C0ki 在 k=0 时为 1、在 k>0 时为 0,两边对得上。
Cnk≡i=0∏sCniki(modp)
□
故事讲完了,能带走什么
推论一:什么时候被 p 整除
由定理立刻得到:Cnk≡0(modp) 当且仅当存在某一位 ki>ni。
用 p 进制减法的话说,这就是k−n 在 p 进制上要借位。
比如 p=2,n=13=(1101)2:k=5=(0101)2 时一位都不缺,C135=1287 是奇数;k=6=(0110)2 时第三位不够,得向高位借位,C136=1716 就是偶数。
这也是 OI 里判零的标准套路:先把 n,k 拆成 p 进制,某一位不够就直接输出 0。
推论二:Freshman's dream 也有画面
(1+x)p≡1+xp 的组合版本,用的其实是同一招:在 p 个位置各填 0 或 1,拧动这 p 个位置构成循环群,轨道大小 1 或 p,而不动点只有“全 0”和“全 1”两种。
所以 0<k<p 时,Cpk 一定是 p 的倍数,只有两个端点活了下来——这正是 Freshman's dream。
同一套工具,把“拧一格”用在 m 行 p 列的方阵上,每一行也是一个轨道——这正是上面那个故事。
推论三:这个定理后来走到了哪里
- 数字组合学:Granville 1997 年的《Binomial coefficients mod a prime power》把模 p 的结论推进到模 pk,中间夹着一层 p-进赋值。
- OI:卢卡斯定理成了模板题(P3807),求 Cnkmodp 时逐位算再相乘,比直接算组合数快得多。
- 另一条线:群表示论里还有个同名的 Frobenius–Lucas 定理,讲的是 p-群不可约特征标的个数。和本文这条线没什么关系,但也都姓 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")结语
回头看,这个证明里最关键的一步,其实只是把“选 k 个”换成了“在群作用下数不动点”。凡是碰到模素数的组合计数,这一招几乎总是第一反应。
不过当年 Lucas 写下这个式子的时候,大概想不到有人能为它编出这样一个故事。他只是顺手记下一个规律,然后转身去研究别的去了。一百多年后我们把它讲成了故事——某种意义上,是我们自己在替它续命。
当然,这个故事谈不上独创:群作用、轨道计数、不动点,Burnside 那一套工具人尽皆知。难的从来不是工具,而是把它摆成一张桌子、一个轮子,让“为什么偏偏是逐位相乘”这件事显形出来。
改天写篇群表示论里那个 Frobenius–Lucas 定理,那才是真正的重头戏。*
*
刚刚那个“改天写”是 AI 自己写的。
不排除人类鸽掉这个的可能。