盧卡斯定理

佇咧數論中，Lucas 定理佇咧算兩項式係數 $ { \ tbinom { m } { n } } $ 被質數 $ p $ 除的所得的數字。

盧卡斯定理頭擺出現佇一八七八年愛德華 ・ 盧卡斯的論文中。

公式

對非負整數 $ m $ 和 $ n $ 佮素數 $ p $，仝餘式 :

$ { \ binom { m } { n } } \ equiv \ prod _ { i=零 } ^ { k } { \ binom { m _ { i } } { n _ { i } } } { \ pmod { p } } , $

成立。其中：

$ m=m _ { k } p ^ { k } + m _ { k 影一 } p ^ { k 影一 } + \ cdots + m _ { 一 } p + m _ { 零 } , $

並且

$ n=n _ { k } p ^ { k } + n _ { k 影一 } p ^ { k 影一 } + \ cdots + n _ { 一 } p + n _ { 零 } $

是 $ m $ 和 $ n $ 的 $ p $ 進位展開。當 $ m < n $ 時，二項式係數 $ { \ tbinom { m } { n } }=零 $。

推論

二項式係數 $ { \ tbinom { m } { n } } $ 可被素數 $ p $ 整除若是唯一佇咧 $ p $ 進位表達下跤 $ n $ 的某一位的數值大於 $ m $ 對應位的數值。 這是庫默爾定理的一个特殊情況。

證明

盧卡斯定理有偌種證明方法。下跤代先交出一種組合方法的證明，然後共出一種因為母函數方法的證明。

組合證明

設 $ M $ 為 $ m $ 元集，共伊做分做 $ m _ { i } $ 咱的長度為 $ p ^ { i } $ 的循環。然後遮的循環中的每一个攏會當單獨輪換，因此作為循環群 $ { C _ { p } } ^ { i } $ 的𥰔仔卡爾積的群 $ G $ 作用佇 $ M $。所以，伊嘛作用佇大細為 _ $ n $ _ 的子集 $ N $。因為 $ G $ 中的元素數量是 $ p $ 的冪，因此伊的任何軌道攏是按呢。所以，為著計算 $ { \ tbinom { m } { n } } $ 模 $ p $，阮只需要考慮這陣作用的不動點。無法度是一寡循環的併集。準確來講，會當通過著 $ k-i $ 的歸納來證明，$ N $ 著愛拄好有 $ n _ { i } $ 咱的長度為 $ p ^ { i } $ 的循環。所以，$ N $ 的數彼號正好是 $ \ prod _ { i=零 } ^ { k } { \ binom { m _ { i } } { n _ { i } } } { \ pmod { p } } $。

因為母函數的證明

本證明由 Nathan Fine 給出。

對素數 $ p $ 和 _ $ n $ _，滿足 $ 一 \ leq n \ leq p 影一 $ , 二項式係數

$ { \ binom { p } { n } }={ \ frac { p \ cdot ( p 影一 ) \ cdots ( p-n + 一 ) } { n \ cdot ( n 影一 ) \ cdots 一 } } $

可被 $ p $ 整除。由此會當，佇母函數內底

$ ( 一 + X ) ^ { p } \ equiv 一 + X ^ { p } { \ pmod { p } } . $

應用數學歸納法可證，對任意非負整數 $ i $，有

$ ( 一 + X ) ^ { p ^ { i } } \ equiv 一 + X ^ { p ^ { i } } { \ pmod { p } } . $

對任意非負整數 $ m $ 佮素數 $ p $，將 $ m $ 用 $ p $ 進位表示，即 $ m=\ sum _ { i=零 } ^ { k } m _ { i } p ^ { i } $，其中 $ k $ _ 為非負整數 _、$ m _ { i } $ 為整數而且 $ 零 \ leq m _ { i } \ leq p 影一 $。注意著

$ { \ begin { aligned } \ sum _ { n=零 } ^ { m } { \ binom { m } { n } } X ^ { n } &=( 一 + X ) ^ { m }=\ prod _ { i=零 } ^ { k } \ left ( ( 一 + X ) ^ { p ^ { i } } \ right ) ^ { m _ { i } } \ \ & \ equiv \ prod _ { i=零 } ^ { k } \ left ( 一 + X ^ { p ^ { i } } \ right ) ^ { m _ { i } }=\ prod _ { i=零 } ^ { k } \ left ( \ sum _ { n _ { i }=零 } ^ { m _ { i } } { \ binom { m _ { i } } { n _ { i } } } X ^ { n _ { i } p ^ { i } } \ right ) \ \ &=\ prod _ { i=零 } ^ { k } \ left ( \ sum _ { n _ { i }=零 } ^ { p 影一 } { \ binom { m _ { i } } { n _ { i } } } X ^ { n _ { i } p ^ { i } } \ right )=\ sum _ { n=零 } ^ { m } \ left ( \ prod _ { i=零 } ^ { k } { \ binom { m _ { i } } { n _ { i } } } \ right ) X ^ { n } { \ pmod { p } } , \ end { aligned } } $

其中 $ n _ { i } $ 是 $ n $ 的 $ p $ 進位表達的第 $ i $ 位。此即證明了本定理。

變型佮推廣

• 二項式係數 $ { \ tbinom { m } { n } } $ 中有質數 $ p $ 的冪次做算式 $ n $ 和 $ m-n $ 佇咧 $ p $ 進位下進行相加計算的進位次數。( 予人叫做庫默爾定理 . )
• Andrew Granville 共盧卡斯定理由素數推廣到矣到素數的冪次。

外部連結

• _ Lucas's Theorem _ at PlanetMath .
• Alternate Proof of Lucas'Theorem