庫默爾定理

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

定理

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

例子

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

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

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

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

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

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

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

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

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

從而存在無窮多個${\displaystyle n}$滿足要求.

綜上，${\displaystyle k}$是任意不為1的整數.

證明

將組合數${\displaystyle {\tbinom {m+n}{m}}}$寫成${\displaystyle {\tbinom {m+n}{m}}={\tfrac {(m+n)!}{m!n!}}}$ 根據勒讓德定理，它所含${\displaystyle p}$的冪次數為 $${\displaystyle \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\}}$$ ${\displaystyle \left[{\frac {n}{p^{i}}}\right]}$等於${\displaystyle n}$在${\displaystyle p}$進制表示下，截去末${\displaystyle i}$位得到的數，因此 $${\displaystyle \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}}}$$ 最後對${\displaystyle i}$求和，就是${\displaystyle m+n}$在${\displaystyle p}$進制下的進位次數。

多項係數的一般化

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

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

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

參見

• 盧卡斯定理