卢卡斯定理

在数论中，盧卡斯定理（）用于计算二项式系数被质数 除的所得的余数。

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

 公式 
对于非负整数和和素数， 同余式:

成立。其中：

并且

是和的进制展开。当时，二项式系数 。

 推论 
二项式系数  可被素数整除当且仅当在进制表达下的某一位的数值大于对应位的数值。
这是 庫默爾定理 的一个特殊情况。

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

 组合证明 
设为元集，将其划分为个长度为的循环。然后这些循环中的每一个都可以单独轮换，因此作为循环群的笛卡尔积的群作用于。因此，它也作用于大小为的子集。由于中的元素数量是的幂，因此它的任何轨道都是如此。因此，为了计算  模，我们只需要考虑这个群作用的不动点。不动点是一些循环的并集。准确地说，可以通过对的归纳来证明，必须恰好有个长度为的循环。因此，的个数正好是 。

 基于母函数的证明 
本证明由Nathan Fine给出。

对于素数和，满足, 二项式系数

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

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

对于任意非负整数和素数，将用进制表示，即 ，其中为非负整数、为整数且。注意到

其中是的进制表达的第位。此即证明了本定理。

 变型和推广 
 二项式系数  中含有质数的幂次为算式和在进制下进行相加计算的进位次数。(被称为庫默爾定理.)
 Andrew Granville将卢卡斯定理由素数推广到了到素数的幂次。

 参考资料

 外部链接

 Alternate Proof of Lucas'Theorem

Category:素數