Lucas 定理证明

Lucas 定理

摘自算法竞赛

对于 $m,n \in \mathbb N$，和素数 $P$，有：

$$\text C_m^n \equiv \prod _{i = 0}^k \text C_{m_i}^{n_i} \pmod P$$

其中，$m=\sum\limits_{i=0}^k P^i \times m_i$，$n=\sum\limits_{i=0}^k P^i \times n_i$，即 $m_i$ 和 $n_i$ 分别是 $m$ 和 $n$ 的 $P$ 进制展开。即对于 $m$ 和 $n$，计算它们 $P$ 进制下每一位的组合数，最后相乘。

特别的，规定当有 $m_i < n_i$ 时，$\text C_{m_i}^{n_i}=0$，此时 $\text C_m^n \bmod P =0$。

上式在编程时的等价式子为：

$$\text C_m^n \equiv \text C_{m \bmod P}^{n \bmod P}\cdot \text C_{\lfloor m /P\rfloor}^{\lfloor n/P\rfloor} \pmod P$$

其可通过递归求得。

证明该公式

证明 对于任一素数 $P$，$n \in [1,P-1]$，有：

$$\text C_{P}^{n}=\frac{P!}{n!\cdot(P-n)!}=\frac{(P-1)!}{(n-1)!\cdot(P-n)!}\times \frac{P}{n}=\text C_{P-1}^{n-1}\times \frac{P}{n}$$

因为 $P$ 为素数，所以 $P$ 与 $n$ 互质，

所以 $P/n$ 中 $P$ 除不掉，$\text C_{P-1}^{n-1}$ 也不能把 $P$ 除掉，必有 $\text C_{P}^{n}=\frac{\text C_{P-1}^{n-1}\times P}{n} \equiv 0 \pmod P$。

将原式代入二项式定理展开式，得：

$$(1+x)^P =\sum\limits_{n = 0}^P \text C_{P}^{n} \times \sout{1^{P-n}}\times x^n = 1+\sum\limits_{n = 1}^{P-1} {\text C_P^n} \times x^n \; +x^P \equiv 1+x^P \pmod P$$

---

下面推导 $\text C_m^n \equiv \text C_{m \bmod P}^{n \bmod P}\cdot \text C_{\lfloor m /P\rfloor}^{\lfloor n/P\rfloor} \pmod P$。

令 $n=sP+q,\;m=tP+r$，$q<P$ 且 $r<P$。

即 $q$，$r$ 分别为 $n$，$m$ 除以 $P$ 的余数，$s$，$t$ 分别为其商。

则待证明式为 $\text C_m^n \equiv \text C_{r}^{q}\cdot \text C_{t}^{s} \pmod P$。

另有：

$$(1+x)^m =(1+x)^{tP+r}=(1+x)^{tP}(1+x)^r \equiv (1+x^P)^t(1+x)^r \\ \equiv (\sum\limits_{i = 0}^t \text{C}_t^i\times x^{iP})\times(\sum\limits_{j = 0}^r \text{C}_r^j\times x^{j}) \pmod P$$

注意第四项前为恒等号。

---

现在我们需要对 $(1+x)^m$，表示其展开后 $x^n$ 项的系数。

假设 $\bmod \;P$ 不存在，因为可以使得 $P$ 与 $x$ 互质。

第一种表达 $x^n$ 项的系数方式为 $\text C_m^n$，由 $(1+x)^m=\sum_{i=0}^m \text C_m^i\cdot x^i$ 得到。

第二种表达方式：

$n=sP+q$，所以 $x^n=x^{sP}\cdot x^q$。因为 $r<P$，所以 $(1+x)^r$ 不可能提供 $x^{sP}$ 项。同理，因为 $P>q$，所以 $(1+x^P)^t$ 不可能提供 $x^q$ 项。

故 $x^n$ 系数的提供是由 $x^{tP}$ 的系数和 $x^r$ 的系数共同相乘提供的。

即 $(1+x^P)^t$ 提供 $x^{sP}$ 项，$(1+x)^r$ 提供 $x^q$ 项。

所以当 $i=s,j=q$ 时，两个系数分别为 $\text C_t^s$ 和 $\text C_r^q$。

得证 $\text C_m^n \equiv \text C_{r}^{q}\cdot \text C_{t}^{s} \pmod P$。