Lucas 定理的简单证明

Lucas 定理

形式： 对于质数 $p$，和非负整数 $n$，$m$，有：

令：$n=(\overline{a_{k-1}a_{k-2}\dots a_2a_1})_p$，表示 $n$ 在 $p$ 进制下的形式。

令：$m=(\overline{b_{k-1}b_{k-2}\dots b_2b_1})_p$，表示 $n$ 在 $p$ 进制下的形式。

那么有：

$$\binom{n}{m}\equiv\prod^{k-1}_{i=0}\binom{a_i}{b_i}\pmod p$$

证明

引理 1

对于多项式 $F(x)$。

$$F(x)^p=F(x^p)$$

证明：

根据数学归纳法，只要证明: $(F(x)+G(x))^p=F(x^p)+G(x^p)$ 即可。

通过二项式定理，有：

$$(F(x)+G(x))^p=\sum_{i=0}^{p}{\binom{p}{i}F(x)^iG(x)^{p-i}}$$

只要再证明 $\forall 1\le x<p$，都满足 $p\mid\binom{p}{x}$ 即可。

显然：

$$\binom p x=\frac{p!}{x!(p-x)!}$$

又因为 $p$ 是质数且 $1\le x<p$ ，所以分子包含质因子 $p$，而分母不包含，因此 $p\mid\binom{p}{x}$。

Lucas

先定义多项式 $F(x)=(1+x)^n\bmod p$，那么 $\binom{n}{m}\bmod p$ 就是 $x^m$ 项的系数。

$$\begin{aligned} F(x)&\equiv(1+x)^n&\pmod p\\ &\equiv\prod_{i=0}^{k-1}(1+x)^{a_ip^i}&\pmod p\\ &\equiv\prod_{i=0}^{k-1}(1+x^{p^i})^{a_i}&\pmod p\\ &\equiv\prod_{i=0}^{k-1}(\sum_{j=0}^{a_i}\binom{a_i}{j}x^{jp^i})&\pmod p\\ \end{aligned}$$

那么显然 $x^m$ 的系数就是 $\prod^{k-1}_{i=0}\binom{a_i}{b_i}\bmod p$，因为对于这 $k-1$ 项中，每一项都只能选择 $\binom{a_i}{b_i}x^{b_ip^i}$。