庫默爾定理

在數學裡，庫默爾定理能計算给出的二项式的系數的Template:Tsl，即 $(\binom{n}{m})$ 含p的幂次。本定理以恩斯特·庫默爾命名。

定理

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

例子

要计算 $ν_{2} ((\binom{10}{3}))$ ，写出 $m = 3$ 和 $n - m = 7$ 的二进制表示 $3 = 1 1_{2}$ 和 $7 = 11 1_{2}$ 。进行二进制加法 $1 1_{2} + 11 1_{2} = 101 0_{2}$ 需要进位三次。故 $(\binom{10}{3}) = 120 = 2^{3} \cdot 15$ 中 2 的次数是 3。

求具有下述性质的所有整数 $k$ ：存在无穷多个正整数 $n$ ，使得 $n + k$ 不整除 $(\binom{2 n}{n})$ 。^[1]

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

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

∴ $n + 1 | (\binom{2 n}{n})$ 对任意正整数 $n$ 成立，从而 1 不满足要求.

当 $k \leq 0$ 时，取 $n = p - k$ （ $p$ 为奇素数， $p > - 2 k$ ），满足要求.

当 $k \geq 2$ 时，取 $k$ 的一个素因子 $p$ ，选取正整数 $m$ 使得 $p^{m} > k$ ，令 $n = p^{m} - k$ ，我们证明： $n + k$ 不整除 $(\binom{2 n}{n})$ .

$2 n = n + n$ 最多进位 $m - 1$ 次. 由库默尔定理， $ν_{p} ((\binom{2 n}{n})) \leq m - 1$ ，

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

从而存在无穷多个 $n$ 满足要求.

综上， $k$ 是任意不为1的整数.

證明

將组合数 $(\binom{m + n}{m})$ 寫成 $(\binom{m + n}{m}) = \frac{(m + n)!}{m! n!}$ 根据勒让德定理，它所含 $p$ 的幂次数为 $\sum_{i = 1}^{\infty} [\frac{m + n}{p^{i}}] - \sum_{i = 1}^{\infty} [\frac{n}{p^{i}}] - \sum_{i = 1}^{\infty} [\frac{m}{p^{i}}] = \sum_{i = 1}^{\infty} {[\frac{m + n}{p^{i}}] - [\frac{n}{p^{i}}] - [\frac{m}{p^{i}}]}$ $[\frac{n}{p^{i}}]$ 等于 $n$ 在 $p$ 进制表示下，截去末 $i$ 位得到的数，因此 $[\frac{m + n}{p^{i}}] - [\frac{n}{p^{i}}] - [\frac{m}{p^{i}}] = {\begin{matrix} 1 & 若第 i + 1 位有进位 \\ 0 & 若第 i + 1 位不进位 \end{matrix}$ 最后对 $i$ 求和，就是 $m + n$ 在 $p$ 进制下的进位次数。

多项系数的一般化

庫默爾定理，可以推广到多项系数 $(\binom{n}{m_{1}, \dots, m_{k}}) : = \frac{n!}{m_{1}! \dots m_{k}!}$ ：

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

$ν_{p} ((\binom{n}{m_{1}, \dots, m_{k}})) = \frac{1}{p - 1} (\sum_{i = 1}^{k} S_{p} (m_{i}) - S_{p} (n))$ .

參見

卢卡斯定理

参考文献

Template:Cite journal

^[2]

[1] Template:Cite journal

[2] Template:Cite web

[1]

[2]

庫默爾定理

目录

定理

例子

證明

多项系数的一般化

參見

参考文献

导航菜单

庫默爾定理

定理

例子

證明

多项系数的一般化

參見

参考文献

导航菜单

搜索