Lucas 定理证明
__vector__ · · 算法·理论
给定
证明
过程
-
前置引理 1。
若
p 为质数，则\binom{p}{i} \mod p 在i=0 或i=p 的情况下为1 ，否则为0 。证明，首先
i=0,i=p 的情况是显然的。其他情况，即
0 \lt i \lt p ，由于p 是质数，p 本身不可能被1,p 以外的数整除。而
i,p-i \lt p ，且\binom{p}{i} 肯定是整数，所以\binom{p}{i} 最后一定包含p 作为因数。结论成立。
-
前置引理 2。
若
p 为质数，则(x+1)^p \equiv x^p+1 \pmod p 。证明，考虑展开。
根据引理 1，$\sum\limits_{i=0}^p \binom{p}{i}x^i \equiv \binom{p}{0}x^0+\binom{p}{p}x^p \equiv 1+x^p \pmod p$。 -
转化
考虑
\binom{n}{m} 和\binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor}\cdot \binom{n \mod p}{m \mod p} 如何对应到同一个式子里面。不难注意到
\binom{n}{m} 是(x+1)^n 的m 次项的系数，即\binom{n}{m} 。通过这一点入手。
设
n=tp+q,m=sp+r 。由引理 2 可得，$((x+1)^p)^t(x+1)^q \equiv (x^p+1)^t(x+1)^q \pmod p$ 。 $(x^p+1)^t(x+1)^q = (\sum\limits_{i=0}^t \binom{t}{i}x^{ip})(\sum\limits_{i=0}^q \binom{q}{i}x^i)$。 由于 $m=sp+r$，所以 $x^m$ 的系数为第一个括号的 $x^{sp}$ 项的系数乘第二个括号的 $x^r$ 项的系数。 即 $x^m$ 的系数等于 $\binom{t}{s}\binom{q}{r} \bmod p$。 现在得到了两条信息：$x^m $ 的系数模 $p$ 同余 $\binom{n}{m}$，$x^m$ 的系数模 $p$ 同余 $\binom{t}{s}\binom{q}{r}$。 lucas 定理得到证明。
思考大概方向
先考虑
然后，通过一系列转化，将
中间比较重要的转化，一个是添加未知量
然后就是利用