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

外部連結

編輯