素数とか素因数分解、中学の数学の最初で習う簡単なことと思われています。論外だが、何かすごそうだが意味は分からないと考える前に分からないと言っている人もいます。
素数とは、自分自身と１以外で割る切れない２以上の整数ってものです。この言葉に関してあまりエレガントではないとか、教科書にかかれている文言と微妙に違うとツッコミが入りそうだが、私は自分の言葉で語れる人のほうが重要だと考えています。
話し戻して、素数の例として７と１１で考えてみます。他にも2,3,5などもありますが、セブンイレブンってことでこの数字を選んでみます。
まず、７に関しては２，３，４，５，６で割り切れません。１１も同様で２，３，４，５，６，７，８，９，１０で割る切ることが出来ません。そう、１と自分自身でしか割り切ることしか出来ません。
ここで、最初の疑問として、「素数に上限が有るか？」って物があります。数学の教科書では「上限がない」ということが簡単な理屈で証明されています。
ここで使われるのは、「とりあえず素数は有限である」と仮定した上で「それを突き崩す」という方法で証明しています。この手法で重要なのは「一つでも反例を見つけ出せれば崩すことができる」という考えです。
「黒いマヌーは存在しない」ということを突き崩すには「黒いマヌー」を１個だけ見つけるだけで十分です。１００個の「黒いマヌー」は不要です。 ただ、一般的な会話ですと一個では不十分らしく大量の反例を求められますが、もし会話がそうなったらこの手の話は綺麗さっぱり終えてください。
ここで素数が無限にあるという証明をするときに行われるのは「仮に上限が有る」素数のリストを作ります
２，３，５，７，１１
で素数が終わりと仮定した場合。その仮定した「すべての素数」をかけ合わせたものに１を加えた数を素因数分解した数字はこのリストにない。だから、「仮に上限が有る」と言うのは間違えであり、「素数の数に上限がない」ということになります。
ちなみに上記の素数のリストを全て掛けて１を足した数字は
2x3x5x7x11+1 = 2311
時間を掛けて2311を素因数分解してもらえば分かるが、これは素数ということになり、そんな数はリストには無いから素数のリストは有限ではないということになります。
言い方を変えれば、どのような素数のリストを作っても、この方法でリストにない素数を計算できてしまうということになります。
実はここからが本題なのだが、素数のリストをかけ合わせた物に１を加算したものは素数である！ということを言う人がいますが、完全な誤解です。
a, b, …, k を任意に与えられた素数のリストとする。その最小公倍数 P ≔ a × b × ⋯ × k に 1 を加えた数 P + 1 は、素数であるか、合成数のいずれかである。素数であれば、最初のリストに含まれない素数が得られたことになる。素数でなければ、何らかの素数 p で割り切れるが、p はやはり最初のリストに含まれない。なぜならば、リスト中の素数は P を割り切るので、P + 1 を割り切ることは不可能だからである。任意の素数のリストから、リストに含まれない新たな素数が得られるので、素数は無数に存在する。（ユークリッド 『原論』第9巻命題20）
って結構分かりやすい言葉で書かれています。
P+1は素数であるか、合成数であるかのどちらかである。そして、素数の場合でも元のリストには無いし、合成数を素因数分解した素数も元にリストにはない。
と、決してP+1が素数だとは断言していません。ただ、P+1は素数であるとユークリッドの説明を斜め読みして伝えている人は多く感じます。
ちなみに先程の例に１３を加えて
2x3x5x7x11x13+1 = 30031
となるが、30031は合成数であり、30031= 59x509 と素因数分解出来ます。ただし、59も509も元にリストに存在しない新たなる素数ということになります。
