小粉兔介绍了一种 Lucas 定理的超级简洁形象的证明，至少是我见过的最简洁的证明。
前置知识：二项式定理。
所用的特殊记号：艾弗森括号、系数提取符 / 系数算子。
Lucas 定理内容：
其中 \(P\) 是质数。
首先我们需要一个结论：
证明：
通过二项式定理拆分左半边：
展开组合数：
把 \((P - 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\)
所以：
（此处中括号表示“艾弗森括号”，即中括号内为真时值为 \(1\) 否则为 \(0\)）
也就是说：
证毕。
然后正式开始证明 Lucas 定理。
首先使用二项式定理，把所求组合数转化为二项式系数：
（此处中括号表示“系数提取符/系数算子”，即表示 \((1 + x)^n\) 中 \(x^m\) 项的系数）
右侧指数可以通过小学除法知识拆分：
设 \(k = \lfloor \frac{n}{P} \rfloor\)，\(r = n \bmod P\)，然后单独看右边被提取系数的式子：
（最后一步用了刚才所证明的结论）
我们把右侧需要提取系数的那个式子单独拿出来，用二项式定理展开：
回到刚才的问题，我们要求这个式子的 \(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}\)
综上所述：
根据定义，\(k = \lfloor \frac{n}{P} \rfloor\)，\(r = n \bmod P\)，所以：
证毕。