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

補題の証明

n$n$ の p$p$ 進数表示を n=n3p3+n2p2+n1p+n0$n=n_3{p}^3+n_2{p}^2+n_{1}p+n_0$ とする。
ルジャンドルの定理より，n!$n!$ が p$p$ で割り切れる回数は，
⌊np⌋+⌊np2⌋+⌊np3⌋=(n3p2+n2p+n1)+(n3p+n2)+n3=n3(1+p+p2)+n2(1+p)+n1=n3p3−1p−1+n2p2−1p−1+n1p−1p−1=1p−1{(n3p3+n2p2+n1p+n0)−(n3+n2+n1+n0)}=n−sp(n)p−1$$\begin{gathered} \lfloor {\displaystyle \frac{n}{p}}\rfloor +\lfloor {\displaystyle \frac{n}{p^2}}\rfloor +\lfloor {\displaystyle \frac{n}{p^3}}\rfloor \\ =(n_3{p}^2+n_{2}p+n_1)+(n_{3}p+n_2)+n_3 \\ =n_3(1+p+p^2)+n_2(1+p)+n_1 \\ =n_3{\displaystyle \frac{p^3-1}{p-1}}+n_2{\displaystyle \frac{p^2-1}{p-1}}+n_1{\displaystyle \frac{p-1}{p-1}} \\ ={\displaystyle \frac{1}{p-1}}\{(n_3{p}^3+n_2{p}^2+n_{1}p+n_0)-(n_3+n_2+n_1+n_0)\} \\ ={\displaystyle \frac{n-s_p(n)}{p-1}} \end{gathered}$$

クンマーの定理の証明

補題より，mCn=m!(m−n)!n!${}_m{\mathrm{C}}_n={\displaystyle \frac{m!}{(m-n)!n!}}$ が素数 p$p$ で割り切れる回数は
(m−sp(m))−((m−n)−sp(m−n))−(n−sp(n))p−1=sp(m−n)+sp(n)−sp(m)p−1$$\begin{gathered} {\displaystyle \frac{(m-s_p(m))-((m-n)-s_p(m-n))-(n-s_p(n))}{p-1}} \\ ={\displaystyle \frac{s_p(m-n)+s_p(n)-s_p(m)}{p-1}} \end{gathered}$$

m−n$m-n$ と n$n$ を p$p$ 進数で足し算したときに繰り上がりが全くないとき，
sp(m−n)+sp(n)=sp(m)$s_p(m-n)+s_p(n)=s_p(m)$ なので定理は正しい。

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