盧卡斯定理

在數論中，盧卡斯定理（英語：Lucas's theorem）用於計算二項式係數${\tbinom {m}{n}}$被質數 $p$除的所得的餘數。

盧卡斯定理首次出現在1878年法國數學家愛德華·盧卡斯的論文中。

公式

對於非負整數$m$和$n$和素數$p$， 同餘式:

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

成立。其中：

$m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},$

並且

$n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}$

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

推論

二項式係數 ${\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=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}$。

基於母函數的證明

本證明由Nathan Fine給出。

對於素數$p$和$n$，滿足$1\leq n\leq p-1$, 二項式係數

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

可被$p$整除。由此可得，在母函數中

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

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

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

對於任意非負整數$m$和素數$p$，將$m$用$p$進制表示，即$m=\sum _{i=0}^{k}m_{i}p^{i}$ ，其中$k$為非負整數、$m_{i}$為整數且$0\leq m_{i}\leq p-1$。注意到

${\begin{aligned}\sum _{n=0}^{m}{\binom {m}{n}}X^{n}&=(1+X)^{m}=\prod _{i=0}^{k}\left((1+X)^{p^{i}}\right)^{m_{i}}\\&\equiv \prod _{i=0}^{k}\left(1+X^{p^{i}}\right)^{m_{i}}=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{m_{i}}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)\\&=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{p-1}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)=\sum _{n=0}^{m}\left(\prod _{i=0}^{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