庫默爾定理

在數學裡，庫默爾定理能計算給出的二項式的系數的p-adic賦值，即${\binom {n}{m}}$含p的冪次。 本定理以恩斯特·庫默爾命名。

定理

庫默爾定理指出，給定整數 $n\geq m\geq 0$和一個質數 $p$, p-adic賦值 $\nu _{p}\left({\tbinom {n}{m}}\right)$ 等於以 $p$ 為基底時$m$加 $n-m$的進位次數。

例子

要計算 $\nu _{2}\left({\tbinom {10}{3}}\right)$，寫出 $m=3$ 和 $n-m=7$ 的二進制表示 $3=11_{2}$ 和 $7=111_{2}$。進行二進制加法 $11_{2}+111_{2}=1010_{2}$ 需要進位三次。 故 ${\tbinom {10}{3}}=120=2^{3}\cdot 15$ 中 2 的次數是 3。

求具有下述性質的所有整數$k$：存在無窮多個正整數$n$，使得$n+k$不整除 ${\binom {2n}{n}}$。

解 ∵ ${\binom {2n}{n-1}}={\frac {2n(2n-1)\cdots (n+2)}{(n-1)!}}={\frac {n}{n+1}}{\binom {2n}{n}}$,

∴ ${\frac {1}{n+1}}{\binom {2n}{n}}={\binom {2n}{n}}-{\binom {2n}{n-1}}$ 是整數，

∴ $n+1\left|{\binom {2n}{n}}\right.$ 對任意正整數$n$成立，從而 1 不滿足要求.

當$k\leq 0$時，取$n=p-k$（$p$為奇素數，$p>-2k$），滿足要求.

當$k\geq 2$時，取$k$的一個素因子$p$，選取正整數$m$使得 $p^{m}>k$，令 $n=p^{m}-k$，我們證明： $n+k$ 不整除 ${\binom {2n}{n}}$.

$2n=n+n$ 最多進位$m-1$次. 由庫默爾定理，$\nu _{p}\left({\binom {2n}{n}}\right)\leq m-1$，

∵ $n+k=p^{m}$，∴ $n+k$不整除${\binom {2n}{n}}$.

從而存在無窮多個$n$滿足要求.

綜上，$k$是任意不為1的整數.

證明

將組合數${\tbinom {m+n}{m}}$寫成${\tbinom {m+n}{m}}={\tfrac {(m+n)!}{m!n!}}$ 根據勒讓德定理，它所含$p$的冪次數為 $$\sum _{i=1}^{\infty }\left[{\frac {m+n}{p^{i}}}\right]-\sum _{i=1}^{\infty }\left[{\frac {n}{p^{i}}}\right]-\sum _{i=1}^{\infty }\left[{\frac {m}{p^{i}}}\right]=\sum _{i=1}^{\infty }\left\{\left[{\frac {m+n}{p^{i}}}\right]-\left[{\frac {n}{p^{i}}}\right]-\left[{\frac {m}{p^{i}}}\right]\right\}$$ $\left[{\frac {n}{p^{i}}}\right]$等於$n$在$p$進制表示下，截去末$i$位得到的數，因此 $$\left[{\frac {m+n}{p^{i}}}\right]-\left[{\frac {n}{p^{i}}}\right]-\left[{\frac {m}{p^{i}}}\right]={\begin{cases}1&{\text{若 第 }}i+1{\text{ 位 有 进 位}}\\0&{\text{若 第 }}i+1{\text{ 位 不 进 位}}\end{cases}}$$ 最後對$i$求和，就是$m+n$在$p$進制下的進位次數。

多項係數的一般化

庫默爾定理，可以推廣到 多項係數 ${\tbinom {n}{m_{1},\ldots ,m_{k}}}:={\tfrac {n!}{m_{1}!\cdots m_{k}!}}$ ：

將 $n$ 以 $p$為基底寫做 $n=n_{0}+n_{1}p+n_{2}p^{2}+\cdots +n_{r}p^{r}$和定義 $S_{p}(n)=n_{0}+n_{1}+\cdots +n_{r}$ 是 $p$ 基底的數位和。 則

$\nu _{p}\left({\dbinom {n}{m_{1},\ldots ,m_{k}}}\right)={\dfrac {1}{p-1}}\left(\sum _{i=1}^{k}S_{p}(m_{i})-S_{p}(n)\right)$.

參見

• 盧卡斯定理

參考文獻

• Kummer, Ernst. Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen. Journal für die reine und angewandte Mathematik. 1852, 44: 93–146. doi:10.1515/crll.1852.44.93.