卢卡斯定理证明

· · 算法·理论

卢卡斯定理即

{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