跳至內容

盧卡斯定理

維基百科,自由的百科全書

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

外部連結