Evolton

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

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

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

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

難易度6/ 10計算量4/ 10目安15分

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

方針

(1) はmが素数であることから,1≦r≦m−1ではrとmが互いに素である点を使う。恒等式rmCr=mm−1Cr−1により各二項係数がmの倍数であることを示し,mC1=mで最大公約数がmを超えないことを押さえる。(2)は問題の指定通りkに関する帰納法で進め,(k+1)m−(k+1)を二項定理で展開して,帰納法の仮定とdmの定義を同時に使う。

解答

(1)

mを素数とする。1≦r≦m−1を任意にとる。このときrはmで割り切れないので,rとmは互いに素である。

二項係数について rmCr=mm−1Cr−1 が成り立つ。右辺はmの倍数であるから,左辺rmCrはmの倍数である。いまrとmは互いに素なので,mCr自身がmの倍数でなければならない。

したがってmC1,mC2,…,mCm−1はいずれもmで割り切れる。よって,これらの最大公約数dmもmの倍数である。一方で mC1=m がこの並びの中に含まれているので,dmはmを超えることはできず,またmを割り切る。以上より dm=m である。

(2)

すべての自然数kについて,km−kがdmで割り切れることを帰納法で示す。

まず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項km−kは帰納法の仮定によりdmで割り切れる。またdmはmC1,mC2,…,mCm−1の最大公約数なので,和に現れる各二項係数はすべてdmで割り切れる。よって右辺全体がdmで割り切れる。

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

総評

難度6、計算量4。目安時間は15分程度で,(1)は「素数だから中間二項係数がmの倍数」という事実を,割り算の言葉だけで済ませずにrmCr=mm−1Cr−1で説明するのが採点上安全である。(2)は問題文が帰納法を指定しているので,二項定理で出る中間係数がすべてdmの倍数であることを明示する。典型的なミスは,mC1=mを使わずdm=mの上限を示し忘れること,展開後に−kの処理を落として係数をずらすことである。

Evolton Pro

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

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

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