【東大型】整数の論証

東大レイヤー／出題テーマ／東大での重要度 ★★★★★

アプリで開く →
進み具合を記録できるアプリ版です（ノード単位の直リンクはありません）

要点

東大の整数は『解を求めよ』より『存在しないことを示せ』『〜であることを示せ』の比重が大きい。つまり証明として完結させる力を測っており、具体例をいくつか確認しただけでは点にならない。使える手段は合同式・因数分解・評価の3つで、どれを選ぶかは問題の形がほぼ決めている。手が止まるのは発想が足りないからではなく、この対応表を持っていないか、小さい場合の実験を飛ばしているかのどちらかである。

こんなときに使う

『割った余り』『倍数である』『存在しない』→ 合同式（法をいくつに取るかが本体）
『積 = 定数』の形に変形できる → 因数分解して約数を調べる
『解をすべて求めよ』で候補が無限にある → 評価で有限化
『すべての自然数 n について』→ 数学的帰納法
素数が絡む → 素数の定義（p が ab を割るなら p は a か b を割る）に戻る
平方数が絡む → mod 3, 4, 8 を試す（平方数の取りうる余りが限られる）

手順

1. 何を示すのかを確定する（存在／非存在／すべての解／ある性質）
2. n = 1, 2, 3 で実験し、構造を掴む（ここを飛ばすと手段を選べない）
3. 3手段のどれが効くか試す。1つで決まらなければ組み合わせる
4. 証明として書く。仮定から結論への流れを切らさない
5. 『〜としてよい』『〜だから〜である』と書いた箇所すべてに根拠があるか点検する

例題

n を自然数とするとき、n² + n + 1 は 5 の倍数にならないことを示せ。

解答

5 の倍数かどうかが問題なので、n を 5 で割った余りで分類する。
n ≡ 0, 1, 2, 3, 4 (mod 5) のいずれかであり、それぞれについて n² + n + 1 を mod 5 で計算する。
n ≡ 0 のとき：0 + 0 + 1 ≡ 1
n ≡ 1 のとき：1 + 1 + 1 ≡ 3
n ≡ 2 のとき：4 + 2 + 1 = 7 ≡ 2
n ≡ 3 のとき：9 + 3 + 1 = 13 ≡ 3
n ≡ 4 のとき：16 + 4 + 1 = 21 ≡ 1
いずれの場合も n² + n + 1 ≢ 0 (mod 5)。
∴ n² + n + 1 は 5 の倍数にならない。（証明終）
【なぜ mod 5 か】問われているのが 5 の倍数性だから。ここは迷う余地がない。
【なぜ5通りで尽くせるか】どんな整数も 5 で割った余りは 0〜4 のいずれかであり、
合同式は積と和を保つので、余りだけで n²+n+1 の余りが決まる。ここが合同式を使う理由そのもの。

別解・ほかの見方

合同式で決まらないときは法を変える（mod 3 で駄目なら mod 4, 8, 9 を試す）
因数分解して積の形にし、約数を全部調べる
評価で有限化してから、残りを合同式で潰す
背理法＋無限降下（『最小の解を取る』と宣言してから議論を始める）
数学的帰納法。示したい命題が弱すぎて回らないときは、より強い命題を立てて帰納する

落とし穴

具体例で確認して満足し、一般の証明を書かない（東大では点にならない）
『x² が3の倍数 ⇒ x が3の倍数』に、3 が素数であることの言及がない
mod の取り方を1つ試して諦める
場合分けが網羅的であることを示さない
合同式で両辺を割ってしまう（法と互いに素なときしか割れない）
具体例で確認して終わりにし、一般の証明を書かない

なぜ大事か

合同式・因数分解・評価の3手段から選ぶ。証明として完結させる力を測ってくる

東大での出方

単独の大問になる年が多く、誘導が薄いのが特徴。(1) で小さい場合を実験させ、(2) で一般の証明を書かせる構成が典型。(1) は答えを出すための問いではなく、(2) の方針を発見させるために置かれている。

確認問題

n³ - n が 6 の倍数であることを示せ
連続する2つの整数は互いに素であることを示せ
n² を 4 で割った余りは 0 か 1 に限ることを示し、それを使って x² + y² = 2003 に整数解がないことを示せ

発展

複数の法を同時に使って絞る。mod 4 と mod 9 の両方の条件を並べると候補が急激に減る。中国剰余定理は範囲外だが、条件を並べて絞るだけなら高校範囲で書ける。

前提になるノード

このノードを前提にするノード

理三の合格ライン（数学 6問中4完+α / 目安80〜100点）

「出題テーマ」のノード

解説は自作です。誤りに気づいたらお問い合わせ（/contact/）から教えてください。

ノード一覧・受験数学マップについて