スポンサーリンク

背理法の問題の解法

背理法を使って証明する問題です。

基本問題

素数が無限個あることを証明しなさい。

解き方

何か仮定し、それによっておこる矛盾を示すことができれば、仮定したことが間違っている事がわかります。
これを利用した証明の方法を「背理法」と言います。

手順としては、証明したい内容とあえて反する事を仮定します。
証明したい内容が正しければ、どこかでほころびが生じるはずです。
問題の条件になっている性質と仮定したことを使って、成り立つことをあげていきます。
矛盾が生じるまで、成り立つ事実を挙げてみてください。

解説

素数が無限個あることを証明しなさい。

「素数が無限個ある」・・・なんともな命題です。
そのまま証明しようと思うと、どうやって無限個あることを示せるのかわからず手を付けられないかもしれません。
背理法を使いましょう。

つまり、「素数が有限個しかない」と仮定します。
この仮定から成り立つことをあげていって、矛盾が示せたら証明になります。

さて、「素数が有限個しかない」という事なので、その有限個の素数を「p_1,p_2,...,p_n」としましょう。
そして自然数aに対しa,a+1が互いに素である事を思い出しましょう。
aがp_1p_2\cots ... \cdot p_nであればp_1p_2\cots ... \cdot p_n+1と互いに素ですね。
p_1p_2\cots ... \cdot p_n+1p_1,p_2,...,p_nのいずれも素因数に持たないことになります。
つまりp_1p_2\cots ... \cdot p_n+1は素数になります。
これは有限個の素数を「p_1,p_2,...,p_n」とした事に反します。
従って「素数が有限個しかない」という仮定が間違っていたので背理法により「素数は無限個である」事が言えます。

ちなみにこのp_1p_2\cots ... \cdot p_n+1が素数なのかというとそれはわかりません。
p_1,p_2,...,p_nには含まれていない素数q_1,q_2の積かもしれません。
それはこの証明では「どうでもいい事」何ですね。
言えているのはp_1p_2\cots ... \cdot p_n+1p_1,p_2,...,p_nで素因数分解できない、という事だけです。

終わりに

背理法は証明の手法として簡潔に証明できる可能性が高いものになります。
中々そのまま証明できないときは候補の1つとして思い出せるようになりましょう。

にほんブログ村 地域生活(街) 東北ブログへ にほんブログ村 地域生活(街) 東北ブログ 米沢情報へ にほんブログ村 教育ブログへ にほんブログ村 教育ブログ 塾教育へ
スポンサーリンク