卢卡斯定理（Lucas定理）的绝妙证明（新版）

从蒟蒻到小犇 · 2024-07-18 00:12:36 · 题解

网上对 Lucas 定理的证明基本上都是用二项式定理或者母函数，不过本蒟蒻发现了一个特别妙的证明。（可惜地方太小了写不下）

Lucas 定理： 当 p 是质数时，

其中 \lfloor~\rfloor 表示向下取整。

前置知识

• 扩展欧几里得定理
• 逆元：当 a 和 p 互质时， a 在 \bmod~p 意义下的逆元唯一。

  证明

我们首先把 C_n^m 写成

上下都是 m 个数，然后分开考虑 p 的倍数部分和不是 p 的倍数的部分。

引理

引理：当 n \bmod p \geq m \bmod p 时，C_n^m 上下（分子和分母） p 的倍数的数量相等；当 n \bmod p < m \bmod p 时， C_n^m 上面分子中 p 的倍数比下面分母中 p 的倍数多一个。

如图，设 p=5，我把 5 的倍数圈了起来，只有当 n=18 或者 n=19 的时候上下 p 的倍数的数量相等，可以感性理解一下，也可以通过比较 \lfloor \frac m p \rfloor 和 \lfloor \frac n p \rfloor - \lfloor \frac {n-m} p \rfloor 来证明。

然后分 n \bmod p \geq m \bmod p 和 n \bmod p < m \bmod p 两种情况讨论。

n \bmod p \geq m \bmod p 的情况

数论里跟取模有关的事情经常会出现循环，那么组合数取模写出来之后也能发现循环，这里我举了 p=3,n=17,m=7 的例子画图，把 C_n^m=\frac{(n-m+1)(n-m+2) \cdots n}{1\times2 \cdots m} 里面的数列了出来，然后把p的倍数圈起来，想分成 p 的倍数和不是 p 的倍数两部分考虑。

图片里圈起来的 p 的倍数部分每个数除以 p 之后就变成连续的一段了，下面分母就是从 1 乘到 \lfloor \frac m p \rfloor，而上面分子是从 \lfloor \frac n p \rfloor 开始往下数，一共 \lfloor \frac m p \rfloor 个数乘起来，所以说这部分就等于C_{\lfloor n/p \rfloor}^{\lfloor m/p \rfloor}。

然后考虑剩下的不是 p 的倍数的部分，根据逆元唯一性，中间除以 p 的余数相同的部分全都可以直接约掉，上下都剩 m \bmod p 个数，上面分子从 n \bmod p 往下数，下面分母从 1 到 m \bmod p，所以这部分就同余于 C_{n \bmod p}^{m \bmod p}。

于是有C_{n}^{m}\equiv C_{\lfloor n/p \rfloor}^{\lfloor m/p \rfloor}\cdot C_{n \bmod p}^{m \bmod p} \pmod p。

n \bmod p < m \bmod p 的情况

类似的，上下都提出来 \lfloor \frac m p \rfloor 个 p 的倍数，就是 C_{\lfloor n/p \rfloor}^{\lfloor m/p \rfloor}。剩下的部分上面分子中有一个 p 的倍数，那么这个数 \bmod~p 就同余于 0，所以说这部分