卢卡斯定理

在数论中，盧卡斯定理（Template:Lang-en）用于计算二项式系数$(\genfrac{}{}{0ex}{}{m}{n})$被质数 $p$除的所得的余数。

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

公式

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

$(\genfrac{}{}{0ex}{}{m}{n})\equiv \prod _{i=0}^k(\genfrac{}{}{0ex}{}{m_i}{n_i})(\mathrm{mod}p),$

成立。其中：

$m=m_k{p}^k+m_{k-1}{p}^{k-1}+\cdots +m_{1}p+m_0,$

并且

$n=n_k{p}^k+n_{k-1}{p}^{k-1}+\cdots +n_{1}p+n_0$

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

推论

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

证明

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

组合证明

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

基于母函数的证明

本证明由Nathan Fine给出。

对于素数$p$和$n$，满足$1\le n\le p-1$, 二项式系数

$(\genfrac{}{}{0ex}{}{p}{n})=\frac{p\cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}$

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

$(1+X{)}^p\equiv 1+X^p(\mathrm{mod}p).$

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

$(1+X{)}^{p^i}\equiv 1+X^{p^i}(\mathrm{mod}p).$

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

$\begin{array}{cc}\sum _{n=0}^m(\genfrac{}{}{0ex}{}{m}{n})X^n& =(1+X{)}^m=\prod _{i=0}^k{((1+X{)}^{p^i})}^{m_i}\\ & \equiv \prod _{i=0}^k{(1+X^{p^i})}^{m_i}=\prod _{i=0}^k\left(\sum _{n_i=0}^{m_i}(\genfrac{}{}{0ex}{}{m_i}{n_i})X^{n_i{p}^i}\right)\\ & =\prod _{i=0}^k\left(\sum _{n_i=0}^{p-1}(\genfrac{}{}{0ex}{}{m_i}{n_i})X^{n_i{p}^i}\right)=\sum _{n=0}^m\left(\prod _{i=0}^k(\genfrac{}{}{0ex}{}{m_i}{n_i})\right)X^n(\mathrm{mod}p),\end{array}$

其中$n_i$是$n$的$p$进制表达的第$i$位。此即证明了本定理。

变型和推广

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

外部链接

• Template:PlanetMath
• Alternate Proof of Lucas'Theorem