素数は無限にあるか

素数が無限にあることの証明は普通次のようにやります。


有限ならば、p1, p2, …, pn と書ける。それらを掛け合わせた結果に 1 を足した数字を考える。


p1 * p2 * … * pn + 1


するとこれは、最大の素数より大きく、かつ素数 p1, p2, …, pn のどれによっても割り切れない。これは矛盾である。仮定は素数が有限であるとしたことだけなので、素数が無限にあることが証明された。


さて、よくわからないので、たとえば、素数が 2, 3, 5, 7, 11, 13 しかなかったとしてこの証明をなぞってみます。

2*3*5*7*11*13 => 30030
30030 + 1 => 30031
factor(30031) => 59 * 509

30031 を因数分解すると、因数分解できますので、素数の積に 1 を足したものが素数だと言っているわけではないようです。因数分解の結果出てくる素数が最初に掛けた素数に含まれていない素数だということなのかな。今の場合で言うと、30031 を因数分解した結果にたとえば 13 が入っていたら、30031 が13 で割り切れてしまうので、30031 を作ったやり方と合っていないことになってしまう。


なんとなくわかってきたのでよしとしよう。