卢卡斯定理

在数论中，盧卡斯定理（英語：Lucas's theorem）用于计算二项式系数${\displaystyle {\tbinom {m}{n}}}$被质数 ${\displaystyle p}$除的所得的余数。

卢卡斯定理首次出现在1878年法國數學家爱德华·卢卡斯^[1]的论文中。

公式

对于非负整数${\displaystyle m}$ 和${\displaystyle n}$ 和素数${\displaystyle p}$ ， 同余式:

${\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},}$ 

成立。其中：

${\displaystyle m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},}$ 

并且

${\displaystyle n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}}$ 

是${\displaystyle m}$ 和${\displaystyle n}$ 的${\displaystyle p}$ 进制展开。当${\displaystyle m<n}$ 时，二项式系数 ${\displaystyle {\tbinom {m}{n}}=0}$ 。

推论

二项式系数 ${\displaystyle {\tbinom {m}{n}}}$  可被素数${\displaystyle p}$ 整除当且仅当在${\displaystyle p}$ 进制表达下${\displaystyle n}$ 的某一位的数值大于${\displaystyle m}$ 对应位的数值。 这是 庫默爾定理 的一个特殊情况。

证明

卢卡斯定理有多种证明方法。 下面首先给出一种组合方法的证明，然后给出了一种基于母函数方法的证明。

组合证明

设${\displaystyle M}$ 为${\displaystyle m}$ 元集，将其划分为${\displaystyle m_{i}}$ 个长度为${\displaystyle p^{i}}$ 的循环。然后这些循环中的每一个都可以单独轮换，因此作为循环群${\displaystyle {C_{p}}^{i}}$ 的笛卡尔积的群${\displaystyle G}$ 作用于${\displaystyle M}$ 。因此，它也作用于大小为${\displaystyle n}$ 的子集${\displaystyle N}$ 。由于${\displaystyle G}$ 中的元素数量是${\displaystyle p}$ 的幂，因此它的任何轨道都是如此。因此，为了计算 ${\displaystyle {\tbinom {m}{n}}}$  模${\displaystyle p}$ ，我们只需要考虑这个群作用的不动点。不动点是一些循环的并集。准确地说，可以通过对${\displaystyle k-i}$ 的归纳来证明，${\displaystyle N}$ 必须恰好有${\displaystyle n_{i}}$ 个长度为${\displaystyle p^{i}}$ 的循环。因此，${\displaystyle N}$ 的个数正好是 ${\displaystyle \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}}$ 。

基于母函数的证明

本证明由Nathan Fine^[2]给出。

对于素数${\displaystyle p}$ 和${\displaystyle n}$ ，满足${\displaystyle 1\leq n\leq p-1}$ , 二项式系数

${\displaystyle {\binom {p}{n}}={\frac {p\cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}}$ 

可被${\displaystyle p}$ 整除。由此可得，在母函数中

${\displaystyle (1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.}$ 

应用数学归纳法可证，对于任意非负整数${\displaystyle i}$ ，有

${\displaystyle (1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.}$ 

对于任意非负整数${\displaystyle m}$ 和素数${\displaystyle p}$ ，将${\displaystyle m}$ 用${\displaystyle p}$ 进制表示，即${\displaystyle m=\sum _{i=0}^{k}m_{i}p^{i}}$  ，其中${\displaystyle k}$ 为非负整数、${\displaystyle m_{i}}$ 为整数且${\displaystyle 0\leq m_{i}\leq p-1}$ 。注意到

${\displaystyle {\begin{aligned}\sum _{n=0}^{m}{\binom {m}{n}}X^{n}&=(1+X)^{m}=\prod _{i=0}^{k}\left((1+X)^{p^{i}}\right)^{m_{i}}\\&\equiv \prod _{i=0}^{k}\left(1+X^{p^{i}}\right)^{m_{i}}=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{m_{i}}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)\\&=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{p-1}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)=\sum _{n=0}^{m}\left(\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}},\end{aligned}}}$ 

其中${\displaystyle n_{i}}$ 是${\displaystyle n}$ 的${\displaystyle p}$ 进制表达的第${\displaystyle i}$ 位。此即证明了本定理。

变型和推广

• 二项式系数 ${\displaystyle {\tbinom {m}{n}}}$  中含有质数${\displaystyle p}$ 的幂次为算式${\displaystyle n}$ 和${\displaystyle m-n}$ 在${\displaystyle p}$ 进制下进行相加计算的进位次数。(被称为庫默爾定理.)
• Andrew Granville将卢卡斯定理由素数推广到了到素数的幂次^[3]。

参考资料

1. Edouard Lucas. Théorie des Fonctions Numériques Simplement Périodiques. American Journal of Mathematics. 1878, 1 (2): 184–196. JSTOR 2369308. MR 1505161. doi:10.2307/2369308.  (part 1);
2. Fine, Nathan. Binomial coefficients modulo a prime. American Mathematical Monthly. 1947, 54: 589–592. doi:10.2307/2304500. 
3. Andrew Granville. (PDF). Canadian Mathematical Society Conference Proceedings. 1997, 20: 253–275 [2016-09-30]. MR 1483922. （原始内容 (PDF)存档于2017-02-02）. 

外部链接

• Lucas's Theorem at PlanetMath.
• Alternate Proof of Lucas'Theorem