クンマーの定理とその証明

$70=2^6+2^2+2$ より，$77-7=70$ の二進数表示は $1000110$

$7$ の二進数表示は $111$

これを二進数として足し算すると繰り上がりは2回（右から2つめの桁と3つめの桁で起こる）。

よって ${}_{77}\mathrm{C}_{7}$ は $2$ で2回割り切れる。

$n$ の $p$ 進数表示を $n=n_3p^3+n_2p^2+n_1p+n_0$ とする。

ルジャンドルの定理より，$n!$ が $p$ で割り切れる回数は，

$\left\lfloor\dfrac{n}{p}\right\rfloor+\left\lfloor\dfrac{n}{p^2}\right\rfloor+\left\lfloor\dfrac{n}{p^3}\right\rfloor\\ =(n_3p^2+n_2p+n_1)+(n_3p+n_2)+n_3\\ =n_3(1+p+p^2)+n_2(1+p)+n_1\\ =n_3\dfrac{p^3-1}{p-1}+n_2\dfrac{p^2-1}{p-1}+n_1\dfrac{p-1}{p-1}\\ =\dfrac{1}{p-1}\{(n_3p^3+n_2p^2+n_1p+n_0)-(n_3+n_2+n_1+n_0)\}\\ =\dfrac{n-s_p(n)}{p-1}$

補題より，${}_m\mathrm{C}_n=\dfrac{m!}{(m-n)!n!}$ が素数 $p$ で割り切れる回数は

$\dfrac{(m-s_p(m))-((m-n)-s_p(m-n))-(n-s_p(n))}{p-1}\\ =\dfrac{s_p(m-n)+s_p(n)-s_p(m)}{p-1}$

$m-n$ と $n$ を $p$ 進数で足し算したときに繰り上がりが全くないとき，

$s_p(m-n)+s_p(n)=s_p(m)$ なので定理は正しい。

さらに，繰り上がりがあるごとに，$s_p(m-n)+s_p(n)-s_p(m)$ は $p-1$ ずつ増える（繰り上がる桁について $s_p(m)$ は $p$ だけ小さくなるが，次の桁に $1$ 追加される）ので定理は正しい。