盧卡斯定理

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

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

公式

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

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

成立。其中：

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

並且

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

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

推論

二項式係數 ${\displaystyle {\tbinom {m}{n}}}$ 可被素數${\displaystyle p}$整除當且僅當在${\displaystyle p}$進制表達下${\displaystyle n}$的某一位的數值大於${\displaystyle m}$對應位的數值。 這是 庫默爾定理 的一個特殊情況。

證明

盧卡斯定理有多種證明方法。 下面首先給出一種組合方法的證明，然後給出了一種基於母函數方法的證明。

組合證明

設${\displaystyle M}$為${\displaystyle m}$元集，將其劃分為${\displaystyle m_{i}}$個長度為${\displaystyle p^{i}}$的循環。然後這些循環中的每一個都可以單獨輪換，因此作為循環群${\displaystyle {C_{p}}^{i}}$的笛卡爾積的群${\displaystyle G}$作用於${\displaystyle M}$。因此，它也作用於大小為${\displaystyle n}$的子集${\displaystyle N}$。由於${\displaystyle G}$中的元素數量是${\displaystyle p}$的冪，因此它的任何軌道都是如此。因此，為了計算 ${\displaystyle {\tbinom {m}{n}}}$ 模${\displaystyle p}$，我們只需要考慮這個群作用的不動點。不動點是一些循環的併集。準確地說，可以通過對${\displaystyle k-i}$的歸納來證明，${\displaystyle N}$必須恰好有${\displaystyle n_{i}}$個長度為${\displaystyle p^{i}}$的循環。因此，${\displaystyle N}$的個數正好是 ${\displaystyle \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}}$。

基於母函數的證明

本證明由Nathan Fine^[2]給出。

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

變型和推廣

• 二項式係數 ${\displaystyle {\tbinom {m}{n}}}$ 中含有質數${\displaystyle p}$的冪次為算式${\displaystyle n}$和${\displaystyle m-n}$在${\displaystyle p}$進制下進行相加計算的進位次數。(被稱為庫默爾定理.)
• Andrew Granville將盧卡斯定理由素數推廣到了到素數的冪次^[3]。