1. 高校数学の美しい物語
  2. クンマーの定理とその証明

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

更新日時 2021/03/07
クンマーの定理(Kummer's theorem)

mCn{}_m\mathrm{C}_n が素数 pp で割り切れる回数は mnm-nnnpp 進数表示して足し算をしたときの繰り上がりの回数と等しい。

整数の美しい定理です!

目次
  • 具体例

  • 証明(前半)

  • 証明(後半)

具体例

例題

77C7{}_{77}\mathrm{C}_{7}22 で何回割り切れるか?

解答

70=26+22+270=2^6+2^2+2 より,777=7077-7=70 の二進数表示は 10001101000110

77 の二進数表示は 111111

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

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

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

証明(前半)

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

補題

n!n!pp で割り切れる回数は nsp(n)p1\dfrac{n-s_p(n)}{p-1}

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

補題の証明

nnpp 進数表示を n=n3p3+n2p2+n1p+n0n=n_3p^3+n_2p^2+n_1p+n_0 とする。

ルジャンドルの定理より,n!n!pp で割り切れる回数は,

np+np2+np3=(n3p2+n2p+n1)+(n3p+n2)+n3=n3(1+p+p2)+n2(1+p)+n1=n3p31p1+n2p21p1+n1p1p1=1p1{(n3p3+n2p2+n1p+n0)(n3+n2+n1+n0)}=nsp(n)p1\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}

証明(後半)

クンマーの定理の証明

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

(msp(m))((mn)sp(mn))(nsp(n))p1=sp(mn)+sp(n)sp(m)p1\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}

mnm-nnnpp 進数で足し算したときに繰り上がりが全くないとき,

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

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

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

人気記事
  1. 高校数学の美しい物語
  2. クンマーの定理とその証明