受験数学わんこらスクール
京大理学部で数学をやったわんこらが中学生や高校生、受験生に数学の公式や問題を解説します。

二項係数の整数問題、東京大学2009年度の理系第1問、文系第2問の解説
今日も吉野家行ってきて、全部数学してきたった。

東京大学2009年度理系第1問と文系の第2問の解説やります。


[問題]
090305_m1.jpg
自然数m≧2に対し、m-1個の二項係数
m_C_1,m_C_2,…,m_C_(m-1)
を考え、これらすべての最大公約数をd_mとする。
すなわちd_mはこれらすべてを割り切る最大の自然数である。
(1)mが素数ならば、d_m=mであることを示せ。
(2)すべての自然数kに対し、k^m-kがd_mで割り切れることを、kに関する数学的帰納法によって示せ。(文系はここまで)
(3)mが偶数のときd_mは1または2であることを示せ。



[解答と解説]
(1)
090305_m2.jpg
m_C_1=mは素数ってことはmの約数は1かmってことだからd_mは1かmかのどっちかです。
だから残りのm_C_2,…,m_C_(m-1)がmの倍数ならばd_m=mになります。

1≦j≦m-1となる整数jに対して
m_C_j=(m(m-1)(m-2)…(m-j))/(j(j-1)(j-2)…1)
=m/j・(m-1)_C_(j-1)
これはなんやかんやでよくやる変形ですね。

j<mでmは素数だからjとmは互いに素です。

だからm/j既約分数なので
m_C_j=m・{(m-1)_C_(j-1)/j}
でm_C_jは整数だから{(m-1)_C_(j-1)/j}も整数でmの倍数になります。

よってd_m=mとわかりました。


090305_m3.jpg
(2)(i)k=1の時
1^m-1=0
で0だからd_mで割り切れます。
(ii)k=jの時、題意成立を仮定します。
つまりj^m-jはd_mで割り切れると仮定します。

するとk=j+1の形を考えて
(j+1)^m-(j+1)
=∑(j=1~m-1)j^i・m_C_j+1+j^m-(j+1)
=∑(j=1~m-1)j^i・m_C_j+(j^m-j)

でm_C_j(j=1~m-1)はd_mで割り切れて、j^m-jは仮定よりd_mで割り切れるからk=j+1の時も題意成立。
(i)(ii)から数学的帰納法より題意成立します。


ここまでは、だいたい色々な問題をやってきて経験を積めばどこかでやったことあるような感じで出来ると思います。
文系はここまでです。


しかし理系の(3)はちょっとキツイです。
飛ばすのが無難やとは思います。

数学の問題のお決まりとして、きっと(2)の
すべての自然数kに対し、k^m-kがd_mで割り切れる
ことを使うと思います。

どうやったら、使えるんか考えてみます。

こういうのは具体的に考えてみると、わかってきたりします。

090305_m4.jpg

mは偶数だからm=2p(pを自然数)とおいて
k=1では
1^(2p)-1=0
は使えないとして
k=2では
2^(2p)-2=4^p-2
これから3,4,5,6,…で割り切れないとかわかると、d_m=1または2とわかりますが
k=2では3では割り切れないのではないかと思ってやみると

4^p-2=(1+3)^p-2
=∑(j=1~p)3^j・p_C_j+1-2
=∑(j=1~p)3^j・p_C_j-3+2
だから3で割ると2余ることがわかります。

k=3では
3^(2p)-3=9^p-3
は4で割り切れないのではないか?って思って4で割ってみると

9^p-3=(5+4)^p-3
=∑(j=1~p)4^j・p_C_j+5-3
=∑(j=1~p)3^j・p_C_j+2

で4で割ると2余ることがわります。

するとk^(2p)-kはk+1で割ったら2余るってことが証明できるのではないか?って予想が立ちます。
そうすればk≧2で考えていますがd_m≧3とするとk+1=d_mつまりk=d_m-1となるkが存在してk^m-kをd_mで割ると2余るから矛盾して、d_m≦2とわかります。

それを解答にしてみると

090305_m5.jpg

pを自然数としてm=2pとおけて

k^(2p)-k=(k^2)^p-k
=(k^2-k-1+k+1)^p-k
=∑(j=1~p)p_C_j・(k^2-k-1)(k+1)^j+k^2-2k-1
=∑(j=1~p)p_C_j・(k^2-k-1)(k+1)^j+(k+1)^2-4(k+1)+2

よって、k^(2p)-kをk+1(k≧2)で割った余りは2です。
したがってd_m≧3と仮定すると
k+1=d_mとなるk(k≧2)が存在して、k^m-kをd_mで割ると2余り(2)に矛盾する。
よって
d_m=1または2


これでも求まりましたがk+1=d_mからk=d_m-1ですが、この時のk^m-kを考えるともっと簡単に分かります。

090305_m6.jpg

k=d_m-1の時

(d_m-1)^(2p)-(d_m-1)
=∑(j=1~2p)d_m^j・(-1)^(2p-j)・(2p)_C_j
+(-1)^(2p)-d_m+1
=d_m(∑(j=1~2p)d_m^(j-1)・(-1)^(2p-j)・(2p)_C_j-1)
+2
でこれをd_mは割り切るので、2はd_mで割りきれます。
だからd_m=1または2です。

これはk=d_m-1とするのは、ちょっといきなりは思いつきにくいですね。

(3)の別解→a+b=1の時、a,bは互いに素

高校数学の入試問題などの解説

東京大学の入試の数学の過去問の解説

整数問題の解法の解説と問題演習




テーマ:大学受験 - ジャンル:学校・教育

▲ページトップへ
この記事に対するトラックバック
トラックバックURL
→http://kazuschool.blog94.fc2.com/tb.php/237-8e4a8cc6
この記事にトラックバックする(FC2ブログユーザー)
▲ページトップへ
プロフィール

Author:わんこら
京都大学理学部で数学と物理を勉強し、数学を専攻しました。
東京で数学と物理の講師やってます

わんこら日記で日記とか勉強の仕方とか書いています

わんこら式数学の勉強法

メール
迷惑メールにされる危険性があるので出来るだけ
kazuyuki_ht○guitar.ocn.ne.jp
(○を@にしてください)に送ってください
勉強とかでどんな悩み持ってるかなど色々と教えてくれると嬉しいです。
わんこら式のやり方についてのメールはわんこら式診断プログラムを参考にしてください

詳しいプロフィール

人気blogランキングへ



にほんブログ村 受験ブログへ



学生広場

相互リンクも募集してます。

何かあれば
kazuschool_ht★yahoo.co.jp
かメールフォームからメールください。
(★を@にしてください)

カテゴリー

メールフォーム

名前:
メール:
件名:
本文:

FC2カウンター

リンク

このブログをリンクに追加する

お勧めの参考書、ノート

数学でお勧めのノートは
KOKUYOの無地
理由




センター試験は過去問が大切


チャートが終わったらお勧め
大学への数学1対1シリーズ
数学1


数学A


数学2


数学B


数学3


数学C

月別アーカイブ

ブログ内検索

RSSフィード

最近のトラックバック

ブロとも申請フォーム

この人とブロともになる

  1. 無料アクセス解析