本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-22 15:52:30

给定 $n,m,p$，保证 $p$ 是质数。

证明 $\binom{n}{m} \equiv \binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor}\cdot \binom{n \mod p}{m \mod p} \pmod p$。

过程

1. 前置引理 1。

   若 $p$ 为质数，则 $\binom{p}{i} \mod p$ 在 $i=0$ 或 $i=p$ 的情况下为 $1$，否则为 $0$。

   证明，首先 $i=0,i=p$ 的情况是显然的。

   其他情况，即 $0 \lt i \lt p$，由于 $p$ 是质数，$p$ 本身不可能被 $1,p$ 以外的数整除。

   而 $i,p-i \lt p$，且 $\binom{p}{i}$ 肯定是整数，所以 $\binom{p}{i}$ 最后一定包含 $p$ 作为因数。

   结论成立。

2. 前置引理 2。

   若 $p$ 为质数，则 $(x+1)^p \equiv x^p+1 \pmod p$。

   证明，考虑展开。

   $(x+1)^p = \sum\limits_{i=0}^p\binom{p}{i}x^i$。

   根据引理 1，$\sum\limits_{i=0}^p \binom{p}{i}x^i \equiv \binom{p}{0}x^0+\binom{p}{p}x^p \equiv 1+x^p \pmod p$。

3. 转化

   考虑 $\binom{n}{m}$ 和 $\binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor}\cdot \binom{n \mod p}{m \mod p}$ 如何对应到同一个式子里面。

   不难注意到 $\binom{n}{m}$ 是 $(x+1)^n$ 的 $m$ 次项的系数，即 $\binom{n}{m}$。

   通过这一点入手。

   设 $n=tp+q,m=sp+r$。

   $(x+1)^n = (x+1)^{tp+q} = ((x+1)^p)^t(x+1)^q$ 。

   由引理 2 可得，$((x+1)^p)^t(x+1)^q \equiv (x^p+1)^t(x+1)^q \pmod p$ 。

   $(x^p+1)^t(x+1)^q = (\sum\limits_{i=0}^t \binom{t}{i}x^{ip})(\sum\limits_{i=0}^q \binom{q}{i}x^i)$。

   由于 $m=sp+r$，所以 $x^m$ 的系数为第一个括号的 $x^{sp}$ 项的系数乘第二个括号的 $x^r$ 项的系数。

   即 $x^m$ 的系数等于 $\binom{t}{s}\binom{q}{r} \bmod p$。

   现在得到了两条信息：$x^m $ 的系数模 $p$ 同余 $\binom{n}{m}$，$x^m$ 的系数模 $p$ 同余 $\binom{t}{s}\binom{q}{r}$。

   lucas 定理得到证明。

思考大概方向

先考虑 $\binom{n}{m}$ 的实际含义，或者说将其对应到某个值。

然后，通过一系列转化，将 $\binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor}\cdot \binom{n \mod p}{m \mod p}$ 也对应到这个值。

中间比较重要的转化，一个是添加未知量 $t,q,r,s$ ，将 $n,m$ 用含 $p$ 的式子表示出来，并将 $(x+1)^n \bmod p$ 用这几个变量表示，转化。

然后就是利用 $p$ 为质数的性质，将这个式子进行简化，并展开为两个幂次分别为 $t,q$ 的二项式的乘积，随后计算出 $x$ 的 $m$ 次项对应的系数，完成证明 lucas 定理。