実は背理法ではない、ユークリッドの素数が無限にあることの証明

ますぴー

「素数が無限にある」というのはあまりにも有名な事実ですが、これの証明の中で最も有名なのは、ユークリッドによるとされる以下のようなものでしょう。

素数が有限個しかないと仮定し、それを $${p_1,p_2,⋯ ,p_n​}$$ とする。
$${N = p_1p_2⋯p_n+1}$$であるような$${N}$$を考えると、
$${N}$$は$${p_1,p_2,⋯ ,p_n​}$$のいずれでも割り切ることができないため、
「$${N}$$は素数である」か「$${N}$$は素数でなく、$${p_1,p_2,⋯ ,p_n​}$$以外の素因数を持つ」かのいずれかである。
どちらの場合でも仮定と矛盾するため、素数は無限に存在する。

ユークリッドによるとされる証明

しかし、この「よく言われる」証明に対して、以下のような疑問が提示されているのを見かけました。

このツイートを見ると確かに、少なくとも冒頭で述べたような証明については、「$${N}$$は素数である」という部分は冗長であるように思えます。
(実際、いくつかのサイトでは、このような冗長性が生まれないような書き方がされていました)

つまり冒頭の証明は、実際にはこのように書くのが自然ということになります。

素数が有限個しかないと仮定し、それを $${p_1,p_2,⋯ ,p_n​}$$ とする。
$${N = p_1p_2⋯p_n+1}$$であるような$${N}$$を考えると、
$${N}$$は$${p_1,p_2,⋯ ,p_n​}$$のいずれでも割り切ることができないが、
「2以上の整数は素因数を少なくとも一つは持つ」ため、
$${N}$$は$${p_1,p_2,⋯ ,p_n​}$$以外の素因数を持つ。
これは仮定と矛盾するため、素数は無限に存在する。

修正された証明(ツイートにおける証明2)

シンプルになりましたね。

また、ツイートでは以下のような証明も提案されています。

素数が有限個しかないと仮定し、それを $${p_1,p_2,⋯ ,p_n​}$$ とする。
$${N = p_1p_2⋯p_n+1}$$であるような$${N}$$を考えると、
$${N}$$は$${p_1,p_2,⋯ ,p_n​}$$のいずれでも割り切ることができないため、
$${N}$$はいかなる素数でも割り切ることはできない。
これは、「2以上の整数は素因数を少なくとも一つは持つ」ということと矛盾するため、素数は無限に存在する。

ツイートにおける証明1

どちらの場合も、「2以上の整数は素因数を少なくとも一つは持つ」という事実を用い、「$${N}$$は素数である」という論を用いずに証明しています。

また、別の方が「$${N}$$は素数である」という論を用いた証明を提案していました。

素数が有限個しかないと仮定し、それを $${p_1,p_2,⋯ ,p_n​}$$ とする。
$${N = p_1p_2⋯p_n+1}$$であるような$${N}$$を考えると、
・$${N}$$は$${p_1,p_2,⋯ ,p_n​}$$に含まれないため素数ではない
・「2以上の整数nについて、nがn未満のすべての素数で割り切れないならばnは素数である」ことを用いると、$${N}$$は$${N}$$未満のすべての素数$${p_1,p_2,⋯ ,p_n​}$$で割り切ることはできないことから、$${N}$$は素数である
この二つは矛盾するため、素数は無限に存在する。

Nは素数であることを用いた証明

こちらの証明には先ほどのような明らかな冗長性は感じないものの、確かに証明1の最後に(過度に)強い論理を一つ噛ませたような証明にも思えます。


いずれにせよ、ここであげた3つの証明では、「$${N}$$が素数である場合」と「$${N}$$が素数でない場合」の場合分けを行っていないことがわかります。
(「Nは素数であることを用いた証明」も場合分けはしておらず、どちらの場合も導けるいう矛盾を利用しています)
私が考えた限り、「場合分け」を「背理法」とともに使い、このような冗長性が生まれないように証明をするのは難しいように思えました。


さて、色々と引用させていただきましたが、ここまでは前置きです。
問題は、冒頭のような冗長な証明がどこから出てきたのか、ということです。

本当のユークリッドの証明

まず、本当のユークリッドの素数が無限にあることの証明は、冒頭のようなものではありません。
これについては、Wikipediaのものを引用します。

$${a, b, …, k}$$ を任意に与えられた素数のリストとする。
その最小公倍数 $${P ≔ a × b × ⋯ × k}$$ に $${1}$$ を加えた数 $${P + 1}$$ は、素数であるか、合成数のいずれかである。
素数であれば、最初のリストに含まれない素数が得られたことになる。
素数でなければ、何らかの素数 $${p}$$ で割り切れるが、$${p}$$ はやはり最初のリストに含まれない。
なぜならば、リスト中の素数は $${P}$$ を割り切るので、$${P + 1}$$ を割り切ることは不可能だからである。
任意の素数のリストから、リストに含まれない新たな素数が得られるので、素数は無数に存在する。

ユークリッド『原論』第9巻命題20
(Wikipedia/素数が無数に存在することの証明より)

先ほどまでの証明と同じフォーマットで書くなら、以下のようになります。

ある個数(n個)の素数を $${p_1,p_2,⋯ ,p_n​}$$ とする。
$${N = p_1p_2⋯p_n+1}$$であるような$${N}$$を考えると、
$${N}$$は素数であるか素数でないかのどちらかである。
$${N}$$が素数である場合、$${p_1,p_2,⋯ ,p_n​}$$のいずれでもない新たな素数$${N}$$が得られる。
$${N}$$が素数でない場合、$${N}$$は何らかの素数$${p}$$で割り切れるが、これは$${p_1,p_2,⋯ ,p_n​}$$のいずれでもないため、同様に新たな素数$${p}$$が得られる。
ある個数の素数があったとき、そこに含まれない素数を一つ作ることができたので、素数は無限に存在する。

ユークリッドの証明のフォーマットを変えたもの

Wikipediaの記事にもある通り、実はユークリッドの『原論』では背理法は使われていないのです。
「ある個数の素数があったとき、そこに含まれない素数を一つ作ることができる」ということを示すことで、いくらでも素数を作ることができる、つまり素数が無限に存在することを直接的に示したわけですね。

この証明では、「$${N}$$が素数である場合」と「$${N}$$が素数でない場合」との場合分けは、冗長でなく機能しています。

また、中村幸四郎・寺阪英孝・伊東俊太郎・池田美恵翻訳の「ユークリッド原論」では、この証明は以下のように書かれていました。

素数の個数はいかなる定められた素数の個数よりも多い。

定められた個数の素数をA，B，Γとせよ。
A，B，Γより多い個数の素数があると主張する。

A，B，Γに割り切られる最小数がとられたとし，それをΔEとし，ΔEに単位ΔZが加えられたとせよ。そうすればEZは素数であるかないかである。
まず素数であるとせよ。そうすればA，B，Γより多い素数A，B，Γ，EZが見いだされた。
次に，EZが素数でないとせよ。そうすればそれは何らかの素数に割り切られる。素数Hに割り切られるとせよ。HはA，B，Γのいずれとも同じではないと主張する。もし可能ならば，同じであるとせよ。ところがA，B，ΓはΔEを割り切る。したがってHもΔEを割り切るであろう。ところがEZをも割り切る。それゆえHは数であって残りの単位ΔZ 割り切るであろう。これは不合理である。ゆえにHはA，B，Γの一つと同じではない。そして素数であると仮定されている。したがって定められた個数のA，B，Γより多い個数のA，B，Γ，Hが見いだされた。これが証明すべきことであった。

『ユークリッド原論(中村幸四郎・寺阪英孝・伊東俊太郎・池田美恵(訳))』

(ΔE=A×B×Γ，ΔZ=1，EZ=ΔE+ΔZ，実際にはこれに各数の長さの棒が描かれた図が付されている)

内容自体はほとんど先ほどのものと同じですが、先ほど「素数は無数に存在する」と書かれていたのが「素数の個数はいかなる定められた素数の個数よりも多い」となっているところなどは注目すべきポイントでしょう。

もちろんこちらでも背理法は使われていません。


この証明を、「$${N}$$が素数である場合」と「$${N}$$が素数でない場合」との場合分けなしに記述することもできそうです。

ある個数(n個)の素数を $${p_1,p_2,⋯ ,p_n​}$$ とする。
$${N = p_1p_2⋯p_n+1}$$であるような$${N}$$を考え、
(「2以上の整数は素因数を少なくとも一つは持つ」ため、)
$${N}$$の素因数の一つを$${p}$$とする。
$${N}$$は$${p_1,p_2,⋯ ,p_n​}$$のいずれでも割り切ることができないため、
素数$${p}$$は$${p_1,p_2,⋯ ,p_n​}$$のいずれでもない新たな素数であることがわかる。
よって、ある個数の素数があったとき、そこに含まれない素数を一つ作ることができたので、素数は無限に存在する。

ユークリッドの証明の場合分けをなくしたパターン

こちらもスマートになりました。
とはいえ、ユークリッドの証明は具体的な構成手順である上、証明自体もそこまで遠回りにはなっていないので、場合分けの冗長度合いはそこまで高くないようにも感じました。


背理法による証明

では、背理法はどこから出てきたのでしょうか。

先ほどのWikipediaの記事は以下のように続きます。

この証明は、しばしば次のような背理法の形で表現される。

素数の個数が有限と仮定し、$${p_1, … p_n}$$ が素数の全てとする。その積 $${P = p_1 × ⋯ × p_n}$$ に $${1}$$ を加えた数 $${P + 1}$$ は、$${p_1, …, p_n}$$ のいずれでも割り切れないので、素数でなければならない。しかし、これは $${p_1, …, p_n}$$ が素数の全てであるという仮定に反する。よって、仮定が誤りであり、素数は無限に存在する。

Wikipedia/素数が無数に存在することの証明

これは、先ほどの「$${N}$$は素数であることを用いた証明」と一致し、冒頭の証明のような冗長性も持ちません。
(これをユークリッドの証明の別の表現と言ってしまっていいのかについては、やや疑問が残ります)

流石にこの背理法での証明の出所まではわかりませんが、こちらの証明の方がよく出回っているのは、「素数を無限に構成する」よりも、「素数が有限であると仮定する」方が直感的だったからなのでしょうか？
(個人的には背理法を使わない方が直感的な気がします)


冗長な証明はどこから来たのか？

さて、ここまでのことをまとめると、「冒頭のような冗長な証明がどこから出てきたのか」という問いには答えが出せそうです。

つまり、

  1. ユークリッドによる証明では、「背理法を使わず」、「$${N}$$が素数であるかで場合分けをして」証明していた

  2. ユークリッドによる証明を変形したものとして、「背理法を使い」、「$${N}$$が素数であるかで場合分けをせず」、「『$${N}$$が素数であること』を導くことで矛盾を示す」証明が知られるようになった
    (しかし、「$${N}$$が素数であること」を導く必然性はなかった)

  3. この二つが知られるようになった結果、「背理法を使い」、「$${N}$$が素数であるかで場合分けをして」証明するというミックス証明が生まれ、巷ではこのような証明が知られるようになった

という流れによって、冒頭の証明が生まれたと推測できます。


混乱の種は、背理法を用いることによって「本当の自然数とは異なった形の自然数」という前提に立たなければならなくなる、ということでしょう。

様々な場所で例として取り上げられていたのは、「$${N}$$は素数であることを用いた証明」に具体的な値を入れたこのような記述についてです。

素数が$${2,3,5,7,11,13}$$しかないと仮定する。
$${N = 2×3×5×7×11×13+1}$$であるような$${N}$$を考えると、
・$${N}$$は$${2,3,5,7,11,13}$$に含まれないため素数ではない
・「2以上の整数nについて、nがn未満のすべての素数で割り切れないならばnは素数である」ことを用いると、$${N}$$は$${N}$$未満のすべての素数($${2,3,5,7,11,13​}$$)で割り切ることはできないことから、$${N}$$は素数である。
この二つは矛盾するため…

「Nは素数であることを用いた証明」で具体的な数字を用いた場合

実際には、この$${N}$$は$${N = 59×509}$$であるため、「$${N}$$は素数である」という記述はおかしいのではないか、という疑問です。
間違った仮定の上で議論しているので、背理法の途中で誤った結論が現れることはあっても良いものだと思いますが、とはいえ「$${59×509}$$が素数」という奇妙な状況になっているのは事実ですから、混乱の種となるのも仕方がないようにも思えます。


追記

この記事を書いている間に、同じ方がさらにツイートされていたので、こちらも置いておきます。

この記事にあるような内容だけでなく、「冗長である代わりに直感的である」というような考察もされているので、こちらもぜひご覧ください。










数学素人による推測と考察ですので、間違い等あればご指摘いただけると幸いです。

また、この議題は「数学デー」という場所で話し合われたものだそうです。
私はその場にはいませんでしたが、こちらの方も貼っておきます。


いいなと思ったら応援しよう！