小粉兔介绍了一种 Lucas 定理的超级简洁形象的证明，至少是我见过的最简洁的证明。
前置知识：二项式定理。
所用的特殊记号：艾弗森括号、系数提取符/系数算子。
Lucas 定理内容：
\[\binom{n}{m} \equiv \binom{\lfloor n \div P \rfloor}{\lfloor m \div P \rfloor} \binom{n \bmod P}{m \bmod P} \pmod{P}
\]
其中 \(P\) 是质数。
首先我们需要一个结论：
\[(1 + x)^{P} \equiv 1 + x^{P} \pmod{P}
\]
证明：
通过二项式定理拆分左半边：
\[(1 + x)^{P} = \sum_{i = 0}^{P} \binom{P}{i} x^{i}
\]
展开组合数：
\[\binom{P}{i} = \frac{P!}{i! (P - i)!}
\]
把 \((P - i)!\) 除上去：
\[\frac{P!}{i! (P - i)!} = \frac{P (P - 1) \dots (P - i + 1)}{i!}
\]
因为 \(P\) 是质数，所以（当 \(i \neq 0\) 时）分子上的 \(P\) 不会被除了 \(1\) 和 \(P\) 以外的正整数整除。
-
如果 \(i = 0\)，此时分母上的 \(P\) 项根本不存在，\(\binom{P}{i} = \binom{P}{0} = 1\)。
-
如果 \(0 < i < P\)，那么分母上的乘积必然不会出现 \(P\) 因子，分子的 \(P\) 也不会被消去，此时原式被 \(P\) 整除
-
如果 \(i = P\)，那么 \(\binom{P}{i} = \binom{P}{P} = 1\)
所以：
\[\binom{P}{i} \equiv [(i = 0) \parallel (i = P)] \pmod{P}
\]
（此处中括号表示“艾弗森括号”，即中括号内为真时值为 \(1\) 否则为 \(0\)）
也就是说：
\[\begin{aligned}
\sum_{i = 0}^{P} \binom{P}{i} x^{i} &\equiv \sum_{i = 0}^{P} [(i = 0) \parallel (i = P)] x^{i} \\
&\equiv x^0 + x^P \\
(1 + x)^{P} &\equiv 1 + x^{P} \pmod{P}
\end{aligned}
\]
证毕。
然后正式开始证明 Lucas 定理。
首先使用二项式定理，把所求组合数转化为二项式系数：
\[\binom{n}{m} = [x^m](1 + x)^{n}
\]
（此处中括号表示“系数提取符/系数算子”，即表示 \((1 + x)^n\) 中 \(x^m\) 项的系数）
右侧指数可以通过小学除法知识拆分：
\[\begin{aligned}
\binom{n}{m}
&= [x^m](1 + x)^{n} \\
&= [x^m](1 + x)^{ (P \times \lfloor \frac{n}{P} \rfloor) + (n \bmod P) } \\
\end{aligned}
\]
设 \(k = \lfloor \frac{n}{P} \rfloor\)，\(r = n \bmod P\)，然后单独看右边被提取系数的式子：
\[\begin{aligned}
(1 + x)^{ kP + r }
&= (1 + x)^{ kP + r } \\
&= (1 + x)^{kP} \times (1 + x)^r \\
&= \left( (1 + x)^P \right)^k \times (1 + x)^r \\
&\equiv (1 + x^P)^k \times (1 + x)^r \pmod{P}
\end{aligned}
\]
（最后一步用了刚才所证明的结论）
我们把右侧需要提取系数的那个式子单独拿出来，用二项式定理展开：
\[\begin{aligned}
(1 + x^P)^{k} \times (1 + x)^r
&= \left( \sum_{i = 0}^{k} \binom{k}{i} x^{iP} \right) \left( \sum_{i = 0}^{r} \binom{r}{i}x^i \right) \\
&= \sum_{i = 0}^{k} \sum_{j = 0}^{r} \left( \binom{k}{i} x^{iP} \times \binom{r}{j} x^j \right) \\
&= \sum_{i = 0}^{k} \sum_{j = 0}^{r} \left( \binom{k}{i} \binom{r}{j} x^{iP + j} \right)
\end{aligned}
\]
回到刚才的问题，我们要求这个式子的 \(x^m\) 项的系数。
上述求和项的指数可以列成表格：
| \(i \backslash j\) |
\(0\) |
\(1\) |
\(\cdots\) |
\(r\) |
| \(0\) |
\(0\) |
\(1\) |
\(\cdots\) |
\(r\) |
| \(1\) |
\(P\) |
\(P + 1\) |
\(\cdots\) |
\(P + r\) |
| \(\vdots\) |
\(\vdots\) |
\(\vdots\) |
\(\ddots\) |
\(\vdots\) |
| \(k\) |
\(kP\) |
\(kP + 1\) |
\(\cdots\) |
\(kP +r\) |
我们发现，\(j \le r = (n \bmod P) < P\)，所以 \(iP + j < (i + 1) P\)，因此每一行最右侧的数也要比下一行最左侧的数要小。
又因为每一行内部是递增的，所以如果按照外层枚举行，内层枚举列的顺序，整个表格也是单调递增的。
因此表格内的数字两两不重复。所以，\(m\) 在上面表格中出现的次数至多有 \(1\) 次，也就是说 \(x^m\) 的出现次数在原式中也至多有 \(1\) 次。
找到这一次所对应的 \(i, j\) 是容易的。因为 \(iP + j = m\)，所以 \(i = \lfloor m \div P \rfloor, j = m \bmod P\)。
-
当 \(j \le r\) 时，这一项在原式中存在，其系数就是 \(\binom{k}{i} \binom{r}{j}\)。
-
当 \(j > r\) 是，这一项在原式中不存在，其系数为 \(0\)。但是因为此时 \(\binom{r}{j} = 0\)（我们定义当 \(x < y\) 时 \(\binom{x}{y} = 0\)），所以依然可以说其系数为 \(\binom{k}{i} \binom{r}{j}\)
综上所述：
\[\begin{aligned}
\binom{n}{m}
&= [x^m](1 + x)^{n} \\
&\equiv [x^m] \left( \sum_{i = 0}^{k} \sum_{j = 0}^{r} \left( \binom{k}{i} \binom{r}{j} x^{iP + j} \right) \right) \\
&\equiv \binom{k}{\lfloor m \div P \rfloor} \binom{r}{m \bmod P} \pmod{P}
\end{aligned}
\]
根据定义，\(k = \lfloor \frac{n}{P} \rfloor\)，\(r = n \bmod P\)，所以：
\[\binom{n}{m} \equiv \binom{\lfloor n \div P \rfloor}{\lfloor m \div P \rfloor} \binom{n \bmod P}{m \bmod P} \pmod{P}
\]
证毕。
