卢卡斯定理

维基百科,自由的百科全书
跳到导航 跳到搜索

数论中,Lucas定理用于计算二项式系数质数 p 除的所得的余数。

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

公式[编辑]

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

成立。其中:

并且

是m和n的p进制展开。当m < n时,二项式系数 

结论[编辑]

  • 二项式系数  可被素数 p 整除当且仅当在p进制表达下n的某一位的数值大于m对应位的数值。

证明[编辑]

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

组合证明[编辑]

基于母函数的证明[编辑]

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

对于素数p和n,满足1≤np-1, 二项式系数

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

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

对于任意非负整数m和素数p,将m用p进制表示,即 ,其中k为非负整数mi 为整数且 0 ≤ mip-1。注意到

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

变型和推广[编辑]

  • 二项式系数 中含有质数p的幂次为算式n和m-n在p进制下进行相加计算的进位次数。(被称为Kummer's theorem.)
  • 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. MR 1483922. (原始内容 (PDF)存档于2017-02-02). 

外部链接[编辑]