本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-28 17:24:24

卢卡斯定理即

$${n \choose m} \equiv {\lfloor n/p \rfloor \choose \lfloor m/p\rfloor} \cdot {n \bmod p \choose m \bmod p} \pmod p$$

其中 $p$ 是质数

我们用二项式定理证明。

首先，$p$ 是质数，则 $${p\choose n} = p n^{-1} {p-1 \choose n-1} \equiv 0 \pmod p$$

然后有

$$(x+1)^p = \sum\limits_{j=0}^p {p \choose j} x^j \equiv x^p + 1 \pmod p$$

然后构造

$$ \begin{aligned} (x + 1)^m &\equiv (x+1)^{p\lfloor m / p\rfloor + (m \bmod p)} \ &\equiv (x^p + 1)^{m/p} (x+1)^{m \bmod p} \ &\equiv \sum\limits_{j=0}^{\lfloor m/p\rfloor} {\lfloor m/p\rfloor \choose j}x^{jp} \cdot \sum\limits_{k=0}^{m\bmod p}{m \bmod p \choose k}x^k \ &\equiv \sum\limits_{k=0}^{m} {\lfloor m/p\rfloor \choose \lfloor m/k\rfloor}{m \bmod p \choose k \bmod p} \pmod p \end{aligned} $$

又有

$$(x+1)^m =\sum\limits_{k=0}^m {m\choose k}x^k$$

按系数，得证：

$${\lfloor m/p\rfloor\choose \lfloor m/k\rfloor}{m\bmod p\choose k\bmod p} \equiv {m\choose k} \pmod p$$