跳转到内容

卢卡斯定理

维基百科,自由的百科全书

数论中,盧卡斯定理(英語:Lucas's theorem)用于计算二项式系数质数 除的所得的余数。

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

公式

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

成立。其中:

并且

进制展开。当时,二项式系数 

推论

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

证明

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

组合证明

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

基于母函数的证明

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

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

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

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

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

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

变型和推广

  • 二项式系数 中含有质数的幂次为算式进制下进行相加计算的进位次数。(被称为庫默爾定理.)
  • 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. Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers (PDF). Canadian Mathematical Society Conference Proceedings. 1997, 20: 253–275 [2016-09-30]. MR 1483922. (原始内容 (PDF)存档于2017-02-02). 

外部链接