Aggressive Style 5

Aggressive Style 5

昨今はコミケ関係を中心に書いています。同人やニコニコ動画方面で活躍される方の相互リンクをお待ちしています。

今日の問題(3):二項定理や二項係数を利用し、「フェルマーの小定理」を証明する(高校2年生以上推奨)

フェルマーの小定理とは「自然数kと素数mについて,k^m-kはmで割り切れる」という定理だ。調べを進めていくとRSA暗号など暗号理論の架け橋となっているこの定理だが、二項定理や二項係数を使って高校生でも証明できる。以下は東大の過去問を使って、フェルマーの小定理を証明してみる。

問題

引用:東大文科 2009前期[東京大学 数学入試問題過去問 53年分(一部解答例付き)]


証明

「フェルマの小定理:青空学園数学科」さんや「フェルマーの小定理:物理のかぎのしっぽ」さんを見ていると合同式を使って証明しているが、二項係数を使って証明する方法もある。本問は丁寧な説明により、二項係数の扱いがどれだけできるかを試している物と思われる。

(1):1 \leq k \leq (m-1)を満たす自然数kにおいて,


m \choose k=\frac{m(m-1)...(m-k+1)}{k!}

ここでmは素数より、分母はk!で割り切れる。さらにmは素数であるから1〜(m-1)のどの自然数でも割り切ることができず、m \choose 1からm \choose m-k+1において共通の約数mを持つ。さらに{m \choose 1}=mよりm以外1のみしか約数を持たないのでd_m = mとなる q.e.d

(2):f(k)=k^m-kとおく。

[1]:k = 1のとき、f(1) = 1^m - 1 = 1 - 1 = 0より,d_mで割り切れる

[2]:k = lのとき、f(l)d_mで割り切れると仮定すると,k = l+1のとき、


f(k+1) = k^{m+1}-k = (l+1)^m -(l+1)
f(k+1) ={m \choose 0}1+{m \choose 1}l+...+{m \choose m}l^m-(l+1)
f(k+1) ={m \choose 1}l+{m \choose 2}l^2+...+{m \choose m-1}l^{m-1}+(l^m-l)

ここで(l^m-l)d_mで割り切れ、{m \choose 1}l+{m \choose 2}l^2+...+{m \choose m-1}l^{m-1}d_mを約数に持つので、f(l+1)d_mで割り切れる。以上[1][2]よりf(k)d_mで割り切れる q.e.d

尚(2)でmを素数とすると、d_m = mよりf(k)=k^m-k素数mで割り切れる。これをフェルマーの小定理と言う。

とこのように二項定理や二項係数を使って解く問題も大学入試で存在する。特に京都大学が健著で1997年理系の(2),2000年理系の(4)などがこれに当たると思われる。

この他掲載事例

過去記事