素数についてずっと誤解していた話

おととい
·

素数とは、1とその数自身以外に約数を持たない、1以外の正の整数のことです。

2とか3とか5とか7とかですね。

逆に6などは、2や3という約数を持つので素数ではないです。

素数について、次の命題が成り立ちます。

「素数は無数に存在する。」

この命題を証明する方法はいろいろありますが、最も有名なのは次の背理法を用いる方法だと思います。

素数の個数が有限(m個)であると仮定します。素数を小さい順にp1, p2, ..., pmとします。このとき、p1×p2×…×pm+1は素数です。しかし、この素数はpmより真に大きいです。よって、素数は少なくともm+1個存在することになります。これは矛盾です。

以上により、最初の仮定「素数の個数は有限である」が間違っていたことがわかり、素数は無数に存在することが示されました。

ここまでの議論を踏まえて、次の主張は成り立つでしょうか。

「mを正整数とする。素数を小さい順にm個とり、小さい順にp1, p2, ..., pmとおく。このとき、p1×p2×…×pm+1は素数である。」

さっきの証明で、これが素数であることを使ったじゃないか。だから成り立つ。

そう思うかも知れません。

しかしこれは間違いです。

p1×p2×…×pm+1は素数になるとは限りません。

m=2の時は、p1×p2+1=2×3+1=7なので、素数です。m=5までの小さい数で試すと素数になるので、正しそうだと思ってしまうかも知れません。

しかし、m=6、p6=13では、2×3×5×7×11×13+1=30031=59×509なので、素数になりません。

素数が無数にあることを証明するときにp1×p2×…×pm+1が素数であることを使ったのに、実際に計算してみると、p1×p2×…×pm+1が素数でない例が出てくるのは、矛盾してるようにも思えます。

なぜこんなことが起こるのか、それは、証明に背理法を用いていることが原因です。

p1×p2×…×pm+1は素数です。ただしこれは、素数の個数が有限であることを仮定した時の話です。

実際にはこの仮定は間違っているわけなので、間違った仮定から導かれた、「p1×p2×…×pm+1は素数である」という主張は間違っているとも正しいとも言えません。間違っていることもありますし、もしかしたらあってるかも知れないです(今回の例では間違ってますね)。要するに、間違った仮定から引き出せる事実はないのです。

高校のときに件の証明を知って以来、つい最近まで勘違いしていました。

自戒のためにここに書き記しておきます。

@nasa_coffee
稚拙な文章をかっこつけて、無責任に書きます。