2016/01/09

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

分野: 整数問題  レベル: マニアック

クンマーの定理(Kummer’s theorem)
${}_m\mathrm{C}_n$ が素数 $p$ で割り切れる回数は $m-n$ と $n$ を $p$ 進数表示して足し算をしたときの繰り上がりの回数と等しい。

整数の美しい定理です!

具体例

例題

${}_{77}\mathrm{C}_{7}$ は $2$ で何回割り切れるか?

解答

$70=2^6+2^2+2$ より,$77-7=70$ の二進数表示は $1000110$
$7$ の二進数表示は $111$
これを二進数として足し算すると繰り上がりは2回(右から2つめの桁と3つめの桁で起こる)。
よって${}_{77}\mathrm{C}_{7}$ は $2$ で2回割り切れる。

注:二進数表示を素早く求める方法は二進法と十進法の変換方法と計算例を参照して下さい。

証明(前半)

$n$ を $p$ 進数表示したときの各桁の和を $s_p(n)$ と書きます。例えば $s_2(7)=3$ です。クンマーの定理の証明の準備として以下の補題を証明します。

補題:
$n!$ が $p$ で割り切れる回数は $\dfrac{n-s_p(n)}{p-1}$

(分かりやすさのために)$n$ が $p$ 進数表示で4桁である場合について証明します。一般の場合も全く同様です。前提知識としてルジャンドルの定理が必要です。

補題の証明

$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$ 追加される)ので定理は正しい。

パスカルの三角形の性質とフラクタルで紹介した2015年の東大入試の問題は,クンマーの定理を使うと素早く解けます。
分野: 整数問題  レベル: マニアック