背理法の問題の解法

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

見出し

1 基本問題
- 1.1 解き方
  - 1.1.1 解説
2 終わりに

基本問題

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

解き方

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

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

解説

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

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

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

さて、「素数が有限個しかない」という事なので、その有限個の素数を「 $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+1$ は $p_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+1$ が $p_1,p_2,...,p_n$ で素因数分解できない、という事だけです。