卢卡斯定理
对于非负整数\(a\)，\(b\)和质数\(p\)，有
\[C_{a}^{b} \equiv C_{a~mod~p}^{b~mod~p} \cdot C_{\lfloor{a/p}\rfloor}^{\lfloor{b/p}\rfloor}~~\left( {mod~p} \right) \]证明
引理
\[\left( {1 + x} \right)^{p^{\alpha}} \equiv 1 + x^{p^{\alpha}}~~\left( {mod~p} \right) \]当\(\alpha = 0\) 时，显然成立。
当\(\alpha = 1\)时，有
\[\left( {1 + x} \right)^{p} = C_{p}^{0}x^{0} + C_{p}^{1}x^{1} + C_{p}^{2}x^{2} + \cdot \cdot \cdot + C_{p}^{p}x^{p} \]其中
\[C_{p}^{i} = \frac{p!}{\left( {p - i} \right)! \cdot i!} \]由于\(p\)是质数，所以在上式的分母中，不存在可以消去分子中为\(p\)的数，因此当\(i = 1,~2,~...,~p - 1\)时，有
\[C_{p}^{i} = \frac{p!}{\left( {p - i} \right)! \cdot i!} \equiv 0~~\left( {mod~p} \right) \]因此
\[\left( {1 + x} \right)^{p} = C_p^0x^{0} + C_p^1x^{1} + C_p^2x^{2} + \cdot \cdot \cdot + C_{p}^{p}x^{p}\\\equiv C _p^0x^{0} + C_{p}^{p}x^{p} = 1 + x^{p}~~\left( {mod~p} \right) \]即
\[\left( {1 + x} \right)^{p} \equiv 1 + x^{p}~~\left( {mod~p} \right) \]数学归纳法。假设当\(\left( {1 + x} \right)^{p^{\alpha}} \equiv 1 + x^{p^{\alpha}}~~\left( {mod~p} \right)\)成立时，证明\(\left( {1 + x} \right)^{p^{\alpha + 1}} \equiv 1 + x^{p^{\alpha + 1}}~~\left( {mod~p} \right)\)也成立。
\[{1 + x} ^{p^{\alpha + 1}} = \left( \left( {1 + x} \right)^{p^{\alpha}} \right)^{p} \\\ \equiv \left( {1 + x^{p^{\alpha}}} \right)^{p}~~\left( {mod~p} \right) \\\ = C_{p}^{0}\left( x^{p^{\alpha}} \right)^{0} + C \]即
\[\left( {1 + x} \right)^{p^{\alpha + 1}} \equiv 1 + x^{p^{\alpha + 1}}~~\left( {mod~p} \right) \]引理证毕。
接下来我们把\(a\)和\(b\)转换为对应的\(p\)进制数，即
\[\begin{align*} a &= a_{k}p^{k} + a_{k - 1}p^{k - 1} + \cdot \cdot \cdot + a_{0} \\\ b &= b_{k}p^{k} + b_{k - 1}p^{k - 1} + \cdot \cdot \cdot + b_{0} \end{align*} \]如果\(a\)和\(b\)在\(p\)进制下的位数不一样，那么就在位数小的前面补\(0\)，使得他们的位数是一样的。
接着我们有
\[\begin{align*} \left( {1 + x} \right)^{a} &= \left( {1 + x} \right)^{a_{k}~p^{k}~ + ~a_{k - 1}~~p^{k - 1}~ + ~ \cdot \cdot \cdot ~ + ~a_{0}} \\\ &= \left( \left( {1 + x} \right)^{p^{k}} \right)^{a_{k}} \cdot \left( \left( {1 + x} \right)^{p^{k - 1}} \right)^{a_{k - 1}} \cdot ~ \cdot \cdot \cdot ~ \cdot \left( \left( {1 + x} \right)^{p^{0}} \right)^{a_{0}} \\\ &\equiv \left( {1 + x}^{p^{k}} \right)^{a_{k}} \cdot \left( {1 + x}^{p^{k - 1}} \right)^{a_{k - 1}} \cdot ~ \cdot \cdot \cdot ~ \cdot \left( {1 + x} \right)^{a_{0}}~~\left( {mod~p} \right) \end{align*} \]即
\[\left( {1 + x} \right)^{a} \equiv \left( {1 + x}^{p^{k}} \right)^{a_{k}} \cdot \left( {1 + x}^{p^{k - 1}} \right)^{a_{k - 1}} \cdot ~ \cdot \cdot \cdot ~ \cdot \left( {1 + x} \right)^{a_{0}}~~\left( {mod~p} \right) \]我们要知道\(C_{a}^{b}\)的值，其实就是左式展开中的\(x^{b}\)的系数。而在右式中，等价于要知道\(x^{b_{k~}~p^{k}~ + ~b_{k - 1}~~p^{k - 1}~ + ~ \cdot \cdot \cdot ~ + ~b_{0}}\)的系数，即
\[C_{a_{k}}^{b_{k}} \cdot C_{a_{k - 1}}^{b_{k - 1}} \cdot ~ \cdot \cdot \cdot ~ \cdot C_{a_{0}}^{b_{0}} \]其中，\(C_{a_{k}}^{b_{k}}\)为右式\(\left( {1 + x^{p^{k}}} \right)^{a_{k}}\)中\(\left( x^{p^{k}} \right)^{b_{k}}\)的系数，简单来说可以类比成\(C_{a}^{b}\)是\({\left( {1+x} \right)}^{a}\)展开式中\(x^b\)的系数，以此类推。因此有
\[C_{a}^{b} \equiv C_{a_{k}}^{b_{k}} \cdot C_{a_{k - 1}}^{b_{k - 1}} \cdot ~ \cdot \cdot \cdot ~ \cdot C_{a_{0}}^{b_{0}}~~\left( {mod~p} \right) \]为了将上式转换为如下形式
\[C_{a}^{b} \equiv C_{a~mod~p}^{b~mod~p} \cdot C_{\lfloor{a/p}\rfloor}^{\lfloor{b/p}\rfloor}~~\left( {mod~p} \right) \]我们先把
\[C_{a_{k}}^{b_{k}} \cdot C_{a_{k - 1}}^{b_{k - 1}} \cdot ~ \cdot \cdot \cdot ~ \cdot C_{a_{0}}^{b_{0}} \]拆分成\(C_{a_{k}}^{b_{k}} \cdot C_{a_{k - 1}}^{b_{k - 1}} \cdot ~ \cdot \cdot \cdot ~ \cdot C_{a_{1}}^{b_{1}}\)和\(C_{a_{0}}^{b_{0}}\)这两部分。
首先对于\(C_{a_{0}}^{b_{0}}\)，其实它就等于\(C_{a~mod~p}^{b~mod~p}\)，这是因为我们要得到某个数的\(p\)进制数，就要用\(p\)整除这个数，得到一个商和余数；再用\(p\)去除商，又得到一个商和余数，以此类推，直到商为小于\(p\)时为止。以\(a\)为例，把最先得到的余数作为\(p\)进制数的最低位有效位，也就是\(a_{0}\)。我们又知道\(a\)可以表述为这种形式\(a = \left\lfloor \frac{a}{p} \right\rfloor \cdot p + r\)，这里的余数\(r\)正是对应于\(a_{0}\)。以此类推\(b\)也一样。
然后就是\(C_{a_{k}}^{b_{k}} \cdot C_{a_{k - 1}}^{b_{k - 1}} \cdot ~ \cdot \cdot \cdot ~ \cdot C_{a_{1}}^{b_{1}}\)。试想一下，我们是通过把\(a\)，\(b\)转换为\(p\)进制
\[\begin{align*} a &= a_{k}p^{k} + a_{k - 1}p^{k - 1} + \cdot \cdot \cdot + a_{0} \\\ b &= b_{k}p^{k} + b_{k - 1}p^{k - 1} + \cdot \cdot \cdot + b_{0} \end{align*} \]进而推出
\[C_{a}^{b} \equiv C_{a_{k}}^{b_{k}} \cdot C_{a_{k - 1}}^{b_{k - 1}} \cdot ~ \cdot \cdot \cdot ~ \cdot C_{a_{0}}^{b_{0}}~~\left( {mod~p} \right) \]现在我们把\(a\)，\(b\)都右移\(1\)位，得到\(\left\lfloor \frac{a}{p} \right\rfloor\)和\(\left\lfloor \frac{b}{p} \right\rfloor\)，对应的\(p\)进制就是
\[\begin{align*} \left\lfloor \frac{a}{p} \right\rfloor &= a_{k}p^{k - 1} + a_{k - 1}p^{k - 2} + \cdot \cdot \cdot + a_{1} \\\ \left\lfloor \frac{b}{p} \right\rfloor &= b_{k}p^{k - 1} + b_{k - 1}p^{k - 2} + \cdot \cdot \cdot + b_{1} \end{align*} \]用类比的方法，我们就可以得到
\[C_{a_{k}}^{b_{k}} \cdot C_{a_{k - 1}}^{b_{k - 1}} \cdot ~ \cdot \cdot \cdot ~ \cdot C_{a_{1}}^{b_{1}} \equiv C_{\lfloor{a/p}\rfloor}^{\lfloor{b/p}\rfloor}~~\left( {mod~p} \right) \]事实上这是正确的，我们可以从\(C_{\lfloor{a/p}\rfloor}^{\lfloor{b/p}\rfloor}\)入手分析，方法与上面分析\(C_{a}^{b}\)的一样（这也暗示我们可以用递归来求解），同样会得到
\[C_{\lfloor{a/p}\rfloor}^{\lfloor{b/p}\rfloor} \equiv C_{a_{k}}^{b_{k}} \cdot C_{a_{k - 1}}^{b_{k - 1}} \cdot ~ \cdot \cdot \cdot ~ \cdot C_{a_{1}}^{b_{1}}~~\left( {mod~p} \right) \]因此，有
\[C_{a}^{b} \equiv C_{a_{k}}^{b_{k}} \cdot C_{a_{k - 1}}^{b_{k - 1}} \cdot ~ \cdot \cdot \cdot ~ \cdot C_{a_{0}}^{b_{0}} \equiv C_{a~mod~p}^{b~mod~p} \cdot C_{\lfloor{a/p}\rfloor}^{\lfloor{b/p}\rfloor}~~\left( {mod~p} \right) \]定理得证。
标签：lfloor,right,cdot,定理,笔记,equiv,卢卡斯,mod,left From： https://www.cnblogs.com/lewisak/p/18502582