数论中,盧卡斯定理(英語: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). 

外部链接

编辑