クンマーの定理

Summarize Timeline Top Qs Fact Check

整数 n ≥ m ≥ 0 と素数 p に対し、 二項係数 ${\textstyle {\tbinom {n}{m}}}$ が p で割り切れるような最大の回数 ${\textstyle \nu _{p}\!{\tbinom {n}{m}}}$ は m と n-m を底 p で加算した時の繰り上がりの回数と等しい。

また、以下のような同値な表現も存在する。

整数 n の p 進表示を ${\textstyle n=n_{0}+n_{1}p+n_{2}p^{2}+\cdots +n_{r}p^{r}}$とし、桁和 ${\textstyle S_{p}(n):=n_{0}+n_{1}+\cdots +n_{r}}$ を定める。このとき、

$${\displaystyle \nu _{p}\!{\binom {n}{m}}={\dfrac {S_{p}(m)+S_{p}(n-m)-S_{p}(n)}{p-1}}.}$$

この公式は、ルジャンドルの公式^[2]を${\textstyle {\tbinom {n}{m}}={\tfrac {n!}{m!(n-m)!}}}$に適用することで証明できる。

${\textstyle {\tbinom {10}{3}}}$が2で割り切れる最大回数を求める。m = 3 = 11₂, n-m = 7 = 111₂ を p = 2 進法で以下のように加算すると3回繰り上がる。

$${\displaystyle {\begin{array}{ccccc}&_{1}&_{1}&_{1}\\&&&1&1\,_{2}\\+&&1&1&1\,_{2}\\\hline &1&0&1&0\,_{2}\end{array}}}$$

したがって ${\textstyle \nu _{2}\!{\tbinom {10}{3}}=3}$ である。実際 ${\textstyle {\tbinom {10}{3}}=120=2^{3}\cdot 15}$ は2で最大3回割り切れる。

p 進法での桁和を用いても求められる。2進法での3, 7, 10 の桁和はそれぞれ${\textstyle S_{2}(3)=1+1=2}$, ${\textstyle S_{2}(7)=1+1+1=3}$, ${\textstyle S_{2}(10)=1+0+1+0=2}$ なので、

$${\displaystyle \nu _{2}\!{\binom {10}{3}}={\dfrac {S_{2}(3)+S_{2}(7)-S_{2}(10)}{2-1}}={\dfrac {2+3-2}{2-1}}=3.}$$

Summarize Fact Check

クンマーの定理は次のように 多項係数 ${\textstyle {\tbinom {n}{m_{1},\ldots ,m_{k}}}={\tfrac {n!}{m_{1}!\cdots m_{k}!}}}$ にも一般化することができる。

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