京大理系数学過去問の解答

質問

京大2006年理系数学過去問の4番、
「2以上の自然数"n"に対し"n"と"n^2＋2"がともに素数となるのは
"n=3"の場合に限ることを示せ」
という問題ですが、自分の回答と模範解答は違います。
ご指導してもらえないでしょうか。

ー大まかな自分の回答ー
対偶を用いて"n not equal 3"のときn,n^2＋2がどちらか合成数となることを示す。
背理法を用いて
「n=3のときn,n^2＋2がどちらか合成数となる」と仮定する。
n=3のときn,n^2＋2がどちらも合成数にならないことを示す。
よって対偶は真であり、元の命題も真となる。（証明終わり）

特に
背理法の使い方に不安があります。

回答No.3

mis_take · ベストアンサー

「Ｐ ⇒ Ｑ」を背理法で証明するには
「Ｐ かつ not Ｑ」を仮定して「矛盾」を導きます。
（回答２の中の説明は間違いです）
対偶「not Ｑ ⇒ not Ｐ」を背理法で証明するのは
「not Ｑ かつ not not Ｐ」すなわち「not Ｑ かつ Ｐ」を仮定します。
ということは，元の「Ｐ ⇒ Ｑ」を背理法で示すのと全く同じです。

対偶「not Ｑ ⇒ not Ｐ」を示せばよいというのは，背理法
　Ｐ かつ not Ｑ
　not Ｑ ⇒ not Ｐ
　ゆえに Ｐ かつ not Ｐ　： 矛盾
の最初と最後を省略したものに過ぎないからです。

「Ｐ ⇒ Ｑ」を直接証明するときは，「Ｐ」だけを用いて推論を進める
対偶で証明するときは，「not Ｑ」だけを用いて推論を進める
それに対し背理法で証明するときは，「Ｐ」と「not Ｑ」両方を用いる
だから強力なのです。
（迷路を解くとき，スタートとゴール両方から攻めるとよいのに似ています）

京大の問題の解答は次のようになります。
(1) ｎが素数
(2) ｎ^2＋２ が素数
(3) ｎ≠３
を仮定する
(1),(3)より，ｎは３でわりきれない
ゆえに，ｎ^2 を３でわると１余る
…

お礼

丁寧な回答ありがとうございます。
背理法の考えを根本から間違ってたわけですね。

ほかの回答者の方もありがとうございました。

回答No.2

tksmsysh

>対偶を用いて"n not equal 3"のときn,n^2＋2がどちらか合成数となることを示す。
ここまではOKです。厳密に言うと、「n,n^2＋2の『少なくとも一方が』合成数となる」だと思いますが。

>背理法を用いて「n=3のときn,n^2＋2がどちらか合成数となる」と仮定する。
質問者さんの不安が的中、確かにここがおかしいですね。
背理法は「命題：Ｐ⇒Ｑ」が真であることを示すために、「Ｐ⇒notＱ」と仮定して矛盾を導き出す証明法です。
（対偶と似ているので注意！）
質問者さんの場合、Ｐを否定しているため誤りとなります。正しくは「n≠3のときn,n^2＋2がともに素数となる」と仮定する、です。

あとはnを3で割った時の余りで分類して、少なくとも一方が合成数になるということで矛盾を示せば大丈夫です。なぜこのような分類をするかと言うと、それはnに具体的な数値を代入していくに見えてきますよ。

回答No.1

Ginzang

確かに、背理法が変である。
この場合、
「nが3以外の素数のとき、n^2＋2が合成数になる」
ことを示すのがよい。
（模範解答がどうかは知らないが、私はこの方針で解けた。）