無限降下法　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　中学・高校で教わる証明法としては、背理法や数学的帰納法がよく知られている。また、
中学・高校では教えられることはないが、大切な証明法として鳩ノ巣原理を用いた証明法
がある。
　これ以外に無限降下法という証明法があるのだが、なぜかこれも重要な証明法にもか
かわらず、やはり学校で教えられることはない。

　このページでは、無限降下法を用いる証明について、整理したいと思う。

　まず一つの有名な問題について、２つの証明法（背理法および無限降下法）を述べ、そ
の違いを実感してもらうことにしよう。

問題　　 は無理数であることを証明せよ。

（背理法による証明）　　 は無理数でない、すなわち、有理数であると仮定する。
　　　　　　　　　　　このとき、互いに素な自然数 ｍ、ｎ を用いて、　 ＝ｎ/ｍ　と書ける。
　　　　　　　　　　　分母を払って両辺を平方すれば、　２ｍ²＝ｎ²　で、ｎ²　は偶数、すなわ
　　　　　　　　　　　ち、ｎ は偶数となる。そこで、ｎ＝２ｎ₁ （ｎ₁ は自然数）とおいて、上式に
　　　　　　　　　　　代入すると、　２ｍ²＝４ｎ₁²　より、　ｍ²＝２ｎ₁²　となる。
　　　　　　　　　　　よって、ｍ²　は偶数、すなわち、ｍ は偶数となる。
　　　　　　　　　　　　このとき、ｍ、ｎ がともに偶数となり、これは、ｍ、ｎ が互いに素
　　　　　　　　　　であることに矛盾する。
　　　　　　　　　　　　したがって、 は無理数である。（証終）

　　　　　　　　　　　（別証）　　 は無理数でない、すなわち、有理数であると仮定する。
　　　　　　　　　　　　　　　　このとき、互いに素な自然数 ｍ、ｎ を用いて、
　　　　　　　　　　　　　　　　　　　　 ＝ｎ/ｍ
　　　　　　　　　　　　　　　　と書ける。分母を払って両辺を平方すれば、　２ｍ²＝ｎ²
　　　　　　　　　　　　　　　　　左辺の２のべきは奇数で、右辺は偶数となり、素因数分解の
　　　　　　　　　　　　　　　　一意性により、　２ｍ²＝ｎ²　は成り立たない。
　　　　　　　　　　　　　　　　　したがって、 は無理数である。（別証終）

　　　　　　　　　　　（コメント）　今まで、「 は無理数である」ことを示すとき、本証のよう
　　　　　　　　　　　　　　　　　な説明しか考えていませんでしたが、結局は納得できる根拠
　　　　　　　　　　　　　　　　　がしっかりしていればよいと考えれば、「素因数分解の一意
　　　　　　　　　　　　　　　　　性」を用いる別証の方が簡明かなと思う今日この頃です。

（無限降下法による証明）　　 は無理数でない、すなわち、有理数であると仮定する。
　　　　　　　　　　　このとき、ある自然数 ｍ、ｎ を用いて、　 ＝ｎ/ｍ　と書ける。
　　　　　　　　　　　分母を払って両辺を平方すれば、　２ｍ²＝ｎ²　で、ｎ²　は偶数、すなわ
　　　　　　　　　　　ち、ｎ は偶数となる。そこで、ｎ＝２ｎ₁ （ｎ₁ は自然数）とおいて、上式に
　　　　　　　　　　　代入すると、　２ｍ²＝４ｎ₁²　より、　ｍ²＝２ｎ₁²　となる。
　　　　　　　　　　　よって、ｍ²　は偶数、すなわち、ｍ は偶数となる。
　　　　　　　　　　　　そこで、ｍ＝２ｍ₁ （ｍ₁ は自然数）とおける。
　　　　　　　　　　このとき、　 ＝ｎ/ｍ　となる自然数 ｍ、ｎ が存在すれば、
　　　　　　　　　　　　　　　　　　　ｍ₁＝ｍ/２　、ｎ₁＝ｎ/２
　　　　　　　　　　により、ｍ、ｎ より小さい自然数 ｍ₁、ｎ₁ が存在して、
　　　　　　　　　　　　　　　　　 ＝ｎ₁/ｍ₁
　　　　　　　　　　となることが示された。
　　　　　　　　　　このような操作を繰り返すと、自然数 ｍ₁、ｎ₁ はどこまでも小さくす
　　　　　　　　　　ることができる。
　　　　　　　　　　　しかるに、ｍ₁、ｎ₁ は自然数なので、このようなことはありえない。
　　　　　　　　　　　　したがって、 は無理数である。（証終）

　　　　　　　　　　　　（追記）　平成２３年１月２３日付け

　　　　　　　　　　　　　　当ＨＰの読者のＫさんという方よりメールをいただいた。

　　　　　　　　　　　　　上記の無限降下法による証明で、「互いに素な自然数 ｍ、ｎ 」とする
　　　　　　　　　　　　と、背理法による証明と同じになるのではないでしょうか？以前、予備
　　　　　　　　　　　　校の先生から「互いに素」と仮定しなくても証明できると言われて、その
　　　　　　　　　　　　方法を考えていたところ、最近サイモン・シン著「フェルマーの最終定理」
　　　　　　　　　　　　（新潮文庫）を読んで初めて「無限降下法」を知り、その方法がわかった
　　　　　　　　　　　　ところです。

　　　　　　　　　　　　（コメント）　Ｋさん、ご指摘ありがとうございます。平成１７年２月８日付け
　　　　　　　　　　　　　　　　　　でアップしたもので、ほぼ６年ぶりに見直しをしました。ご指摘
　　　　　　　　　　　　　　　　　　された通り、証明の初期段階で「互いに素」を仮定しなくても証
　　　　　　　　　　　　　　　　　　明は成立していますね！早速、上記を修正させていただきまし
　　　　　　　　　　　　　　　　　　た。（上記本文は、修正済みのものです。）


　背理法では、条件命題 ： 「　Ｐ → Ｑ　」（これは、命題 ： 〜（Ｐ∧（〜Ｑ））にトートロジー）が真
であることを示すのに、命題 ： Ｐ∧（〜Ｑ） が偽であることを示している。

　これに対して、無限降下法では、命題が偽と仮定して得られる自然数から、それより小さ
い自然数を作る構成法を示し、かつ、その自然数においてもやはり命題が偽であることを
導き、これが自然数という世界では不可能なことであることから命題が真であることを示し
ている。（上記の、赤文字部分）

　この無限降下法という証明法は、１７世紀の数学者 ピェール・ドゥ・フェルマーが編み出し
たものと言われている。

　この証明法の特徴としては、「〜でない」とか「〜することは不可能である」といった否定的
な結論を示すのに有効な点である。これは、「〜である」とか「〜することができる」と仮定し
て矛盾を導く背理法にどことなく似ている。

　今度は、次の問題について、２つの証明法（数学的帰納法および無限降下法）を述べ、そ
の違いを実感してもらうことにしよう。

問題　　２以上の任意の自然数 ｎ は素因数に分解されることを証明せよ。

（数学的帰納法による証明）　ｎ＝２　のとき、２は素数なので、明らかに成り立つ。
　　　　　　　　　　　　ｎ＝ｋ （ｋ≧２）以下のとき成り立つと仮定する。すなわち、
　　　　　　　　　　　　２≦ｍ≦ｋ である任意の自然数 ｍ は素因数に分解されるものとする。
　　　　　　　　　　　　このとき、ｎ＝ｋ＋１ が素数ならば、明らかに成り立つ。
　　　　　　　　　　　　ｎ＝ｋ＋１ が合成数ならば、
　　　　　　　　　　　　　ｋ＋１＝Ａ・Ｂ　（２≦Ａ≦ｋ、２≦Ｂ≦ｋ）となるＡ、Ｂが存在する。
　　　　　　　　　　　　帰納法の仮定により、Ａ、Ｂは素因数に分解されるので、
　　　　　　　　　　　　　ｋ＋１ も素因数に分解される。
　　　　　　　　　　　　以上から、何れにしても、ｎ＝ｋ＋１ は、素因数に分解される。
　　　　　　　　　　　　よって、ｎ＝ｋ＋１ のときも成り立つ。
　　　　　　　　　　　　　したがって、２以上の任意の自然数 ｎ は素因数に分解される。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（証終）

（無限降下法による証明）　２以上の自然数 ｎ について、ｎ が素数ならば、明らかに成り立
　　　　　　　　　　　　つので、ｎ は合成数とする。このとき、
　　　　　　　　　　　　　ｎ＝ｎ₁・ｎ₂　（２≦ｎ₁＜ｎ、２≦ｎ₂＜ｎ）となるｎ₁、ｎ₂ が存在する。
　　　　　　　　　　　　ｎ₁、ｎ₂ がともに素数ならば明らかに成り立つ。
　　　　　　　　　　　　ｎ₁ または ｎ₂ が合成数ならば、上記の操作を繰り返す。
　　　　　　　　　　　　自然数の性質から、何れは両者とも素数（の積）となる。
　　　　　　　　　　　　　よって、２以上の任意の自然数 ｎ は素因数に分解される。（証終）


　上記の証明を眺めていると、無限降下法による証明は、背理法にも似ているし、数学的
帰納法にも似ていることが分かる。


　読者のために、練習問題を一つあげておこう。

練習　任意の自然数 ｍ、ｎ に対して、２ｍ²＋３ｎ² は平方数にはなり得ないことを示せ。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（解答は、こちらを参照）


（参考文献：Ｍ．ラインズ　著　片山孝次　訳　　数　その意外な表情　（岩波書店））


　九州大学前期理系（２０１４）で、剰余類に関する問題と無限降下法を融合した問題が出題
された。

　以下の問いに答えよ。

（１）　任意の自然数ａに対し、ａ²を３で割った余りは０か１であることを証明せよ。

（２）　自然数ａ、ｂ、ｃがａ²＋ｂ²＝３ｃ²を満たすと仮定すると、ａ、ｂ、ｃはすべて３で割り切れ
　　なければならないことを証明せよ。

（３）　ａ²＋ｂ²＝３ｃ²を満たす自然数ａ、ｂ、ｃは存在しないことを証明せよ。


（証明）（１）　任意の自然数ａに対し、

　　　　　　　　　ａ≡０　（ｍｏｄ　３）　、ａ≡１　（ｍｏｄ　３）　、ａ≡２　（ｍｏｄ　３）

　の何れかが成り立つ。このとき、

　　　　ａ²≡０　（ｍｏｄ　３）　、ａ²≡１　（ｍｏｄ　３）　、ａ²≡１　（ｍｏｄ　３）

　よって、ａ²を３で割った余りは０か１である。

（２）　自然数ａ、ｂ、ｃがａ²＋ｂ²＝３ｃ²を満たすと仮定すると、（１）より、

　　　ａ²≡０　（ｍｏｄ　３）　、ｂ²≡０　（ｍｏｄ　３）　、ｃ²≡０　（ｍｏｄ　３）

　の場合に限る。

　よって、ａ、ｂ、ｃはすべて３で割り切れなければならない。

（３）　ａ²＋ｂ²＝３ｃ²を満たす自然数ａ、ｂ、ｃが存在すると仮定すると、（２）より、

　　　ａ＝３ａ’　、ｂ＝３ｂ’　、ｃ＝３ｃ’　（ａ’、ｂ’、ｃ’は自然数）

　とおける。このとき、　９ａ’²＋９ｂ’²＝２７ｃ’²　より、　ａ^’2＋ｂ’²＝３ｃ’²

　　このような操作を繰り返すと、自然数 ａ’、ｂ’、ｃ’ はどこまでも小さくすることができる。
　しかるに、ａ’、ｂ’、ｃ’ は自然数なので、このようなことはありえない。

　よって、ａ²＋ｂ²＝３ｃ²を満たす自然数ａ、ｂ、ｃは存在しない。　　（証終）


（コメント）　このような問題に対して、受験生は経験豊富とはいえない状況と判断されるので、
　　　　　　正答率がどうであったか、大いに気になるところである。新学習指導要領の数学Ａ
　　　　　　に整数問題の章が起こされたので、今後このような問題は大学入試で頻出される
　　　　　　ものと予想される。