Lucas定理 | wzy的博客

type

Post

status

Published

date

May 1, 2026

slug

lucas

summary

前置

Freshman’s Dream（一年级生的梦想）是指在特征为的代数结构（如模的域）中，恒等式成立。

在初等数论背景下，我们通常证明：若为质数，则对于任意整数，有：

证明过程

该证明的核心在于观察二项式展开式中的各项系数。

1. 二项式定理展开

根据二项式定理，我们有：

2. 分析组合数系数

组合数的公式为：

对于满足的任意整数：

分子包含质因子。

分母是和的乘积。由于是质数且，分母中的每一个相乘的整数都严格小于。

根据欧几里得引理，如果质数整除一个乘积，则它必然整除其中至少一个因子。由于分母中没有一个因子能被整除，因此整个分母不能被整除。

这意味着在化简后的最简分数形式中，分子上的 不会被约去。因此：

Deepseek给出的分析对于成立，这是因为： 1. 组合数公式为。 2. 分子包含质数，所以。 3. 分母中的每个因子都小于，因此在模下不为零。 4. 分子为0，分母不为0，因此，其中不为0。

结论：对于成立。

3. 代入展开式

在模的意义下，展开式中除了第一项和最后一项，其余中间所有项的系数都是的倍数，全部变为：

由于，上式简化为：

证毕

卢卡斯定理（Lucas’s Theorem）是组合数学中一个非常优美的结论，它的证明核心在于利用 二项式展开 在模意义下的特殊性质。

定理陈述

对于质数和任意非负整数：

其中是和的进制表示。

核心预备知识： freshman’s Dream

在模意义下（为质数），对于任意整数，有：

通过数学归纳法可以推广到：

证明步骤

我们要比较中项的系数。

为了理解为什么需要比较中项的系数,根据二项式定理，可以展开为。因此，项的系数就是。比较项的系数，实际上是在比较的值

第一步：对进行分解

为什么要二进制拆分因为要凑出才能得到，只有二进制才可以稳定组合利用的进制表示：

第二步：利用模 p 性质简化

根据上面提到的，我们可以得到：

第三步：展开每一项

利用二项式定理展开等式右边的每一项：

第四步：提取的系数

在右侧的乘积式中，为了凑出，我们需要从每个括号里选出一项，使得它们的幂次之和等于：

由于，这恰好对应了的 p 进制分解。因此，对于给定的，系数序列是唯一的，且必须等于的进制位。

因此，的系数为：

而在等式左边中，的系数定义就是。

结论：

证毕。 # 代码转换

现在得到了怎么转换成代码语言呢，直接分解二进制太麻烦有没有更好的方法呢？ 有的！兄弟有的！ ## 1. 数学层面的拆解

卢卡斯定理的标准形式是：

如果我们只把第一项（最低位）拿出来，剩下的项可以看作是一个整体：

为什么是正好是Lucas的展开呢

剥洋葱模型（视觉化理解）你可以把进制数想象成一个由多层组成的“洋葱”，每一层就是一个的位。 - 第一层（最外层）：我们剥掉和，用 C 函数计算它们。 - 剩下的芯：剩下的部分依然是一个完整的、缩小的“洋葱”。 - 重复动作：既然剩下的部分结构和原来一模一样，我们就可以用同一个函数 Lucas 继续处理它。

一个具体的数值推演

假设，，。

进制分解：

直接展开（Lucas 定理）：

递归程序的执行路径：

第一层调用 Lucas(172, 28)：

返回 C(172%13, 28%13) * Lucas(172/13, 28/13)

即 C(3, 2) * Lucas(13, 2)

第二层调用 Lucas(13, 2)：

返回 C(13%13, 2%13) * Lucas(13/13, 2/13)

即 C(0, 2) * Lucas(1, 0)

第三层调用 Lucas(1, 0)：

返回 1（终止条件）。

最终合起来：

C(3, 2) * C(0, 2) * 1

这与直接展开式完全一致（顺序相反，但乘法交换律不影响结果）。 # 部分代码

但是在计算需要除法，但是模运算是没有除法的，这就要使用费马小定理求逆元

前置