Evolton

東京大学 2009年度 前期日程 第2次学力試験理系数学 第1問

自然数m≧2に対し,m−1個の二項係数mC1,mC2,…,mCm−1を考え,これらすべての最大公約数をdmとする。
すなわちdmはこれらすべてを割り切る最大の自然数である。

(1) mが素数ならば,dm=mであることを示せ。

(2) すべての自然数kに対し,km−kがdmで割り切れることを,kに関する数学的帰納法によって示せ。

(3) mが偶数のときdmは1または2であることを示せ。

難易度7/ 10計算量6/ 10目安25分

整数、場合の数、論証・証明 二項定理、数学的帰納法、素因数分解、場合分け

方針

(1) (2)は文系第2問と同じ構造で,素数の場合はrmCr=mm−1Cr−1,帰納法では二項定理を使う。(3)ではdmに含まれ得る素因数を調べる。奇素数pについてはm=pqvと書き,特定の二項係数mCpqがpで割り切れないことを,分子と分母に現れるpの個数を比較して示す。さらに2について,m=2qvでv>1なら奇数の二項係数を作り,m=2qなら4で割り切れない二項係数を作る。

解答

(1)

mを素数とする。1≦r≦m−1ではrとmは互いに素である。二項係数には rmCr=mm−1Cr−1 という関係があるので,rmCrはmで割り切れる。rとmが互いに素であるから,mCrがmで割り切れる。

よってmC1,mC2,…,mCm−1はすべてmの倍数である。一方でmC1=mであるから,これらの最大公約数はmを超えられない。したがって dm=m である。

(2)

k=1のときは 1m−1=0 なのでdmで割り切れる。

ある自然数kについてkm−kがdmで割り切れると仮定する。二項定理より(k+1)m=km+mC1k+mC2k2+⋯+mCm−1km−1+1であるから(k+1)m−(k+1)=km−k+mC1k+mC2k2+⋯+mCm−1km−1である。右辺第1項は帰納法の仮定によりdmで割り切れる。また,dmの定義により各mCrはdmで割り切れる。したがって右辺全体がdmで割り切れる。

ゆえに(k+1)m−(k+1)もdmで割り切れる。数学的帰納法により,すべての自然数kに対して km−k は dm で割り切れる ことが成り立つ。

(3)

mを偶数とする。まず,dmが奇素数を約数にもたないことを示す。pをmを割る奇素数とし,mを割るpの最大の累乗をpqとする。すなわち m=pqv と書き,vはpで割り切れないとする。mは偶数でpは奇素数なので,pq<mであり,mCpqはdmを考える並びの中に含まれる。

この二項係数をmCpq=m(m−1)(m−2)⋯(m−pq+1)pq(pq−1)(pq−2)⋯1と書き,先頭のm/pq=vを外すとmCpq=v⋅(m−1)(m−2)⋯(m−pq+1)(pq−1)(pq−2)⋯1である。

1≦j≦pq−1について,jがpでちょうどe回割り切れるとする。このときe<qであり,m−j=pqv−j もpでちょうどe回割り切れる。したがって積 (m−1)(m−2)⋯(m−pq+1) に含まれるpの個数は,(pq−1)(pq−2)⋯1 に含まれるpの個数と等しい。さらにvはpで割り切れない。よってmCpqはpで割り切れない。したがってdmは奇素数を約数にもたない。

次に2の因数を調べる。m=2qvと書き,vを奇数とする。v>1の場合,mC2qを考えると,同様にmC2q=v⋅(m−1)(m−2)⋯(m−2q+1)(2q−1)(2q−2)⋯1である。1≦j≦2q−1についてm−jとjに含まれる2の個数は等しく,vは奇数である。したがってmC2qは奇数である。この場合,dmは奇素数も2も約数にもたないので dm=1 である。

残るのはm=2qの場合である。このときmは偶数なのでq≧1である。m=2なら並びは2C1=2だけなのでd2=2である。以下m≧4とする。mCm/2を考えるとmCm/2=2⋅(m−1)(m−2)⋯(m/2+1)(m/2−1)(m/2−2)⋯1である。ここでも1≦j≦m/2−1についてm−jとjに含まれる2の個数は等しいので,分数部分は奇数である。したがってmCm/2は2で割り切れるが4では割り切れない。

以上より,mが偶数のときdmは奇素数を約数にもたず,また4でも割り切れない。したがって dm は 1 または 2 である。

総評

難度7、計算量6。目安時間は25分前後で,(3)の素因数評価が山である。(1)(2)は文系第2問と共通なので,ここを短時間で確実に処理し,(3)に時間を残したい。奇素数pを消すには「dmがすべての二項係数を割る」ことの逆を使い,pで割り切れない二項係数を1つ作ればよい。2についても,mが2の累乗でない場合と2の累乗の場合を分ける。典型的なミスは,pqがmを割る最大の累乗であることを使わず,分子分母の素因数の個数比較を曖昧にすることである。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る東大の整数の問題で問題集を作る

出典: 東京大学 2009年度 前期 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。