青の数学

素数が無限にある証明はユークリッドのものが有名．

素数が有限個だとして，有限個の素数をすべて掛け合わせたものを P とする．
P+1 は，有限個の素数のどれで割っても割り切れない．
したがって，P+1 は初めの有限個の素数のリストでは割り切れない数である．
P+1 は素数であるか合成数であるが，素数であれば新たな素数と言えるし，合成数であっても，最初の有限個の素数にはない新たな素因数を含む数である．
いずれにしても，新たな素数が必要になるので，素数は無数にある．

で，今日，ある人に見せてもらった．「青の数学」という小説に，上記のような説明の場面で，
「P+1 は新たな素数である．」
と断言する台詞があって，のけぞった．ユークリッドの証明の通り合成数もあるよ．

で，反例を求めてみる．
つまり，素数を順にかけたものに +1 した数が素数かどうか．

2 +1 = 3 は素数
2×3 +1 = 7 は素数
2×3×5 +1 = 31 は素数
2×3×5×7 +1 = 211 は素数
2×3×5×7×11 +1 = 2311 は素数
2×3×5×7×11×13 +1 = 30031 = 59×509
と6番目の素数で合成数が見つかる．（ただし，リストにない新たな素数が因数の合成数）

2×3×5×7×11×13×17 +1 = 510511 = 19×97×277
2×3×5×7×11×13×17×19 +1 = 9699691 = 347×27953
以下，
23 まで, 223092871 = 317×703763
29 まで, 6469693231 = 331×571×34231
31 まで, 200560490131 は素数
37 まで, 7420738134811 = 181×60611×67642
41 まで, 304250263527211 = 61×450451×11072701
43 まで, 13082761331670031 = 167×78339888213593
47 まで, 614889782588491411 = 953×46727×13808181181
53 まで, 32589158477190044731 = 73×139×173×18564761860301
59 まで, 1922760350154212639071 = 277×3467×105229×19026377261
61 まで, 117288381359406970983271 = 223×525956867082542470777
67 まで, 7858321551080267055879091 = 54730729297×143581524529603
71 まで, 557940830126698960967415391 = 1063×303049×598841×2892214489673
とまぁ，ほとんど合成数だなー

あるいは，素数を 2 だけからスタートして，この方法で新たな素数を見つけてみる．
2 +1 = 3 は素数
2×3 +1 = 7 は素数
2×3×7 +1 = 43 は素数
2×3×7×43 +1 = 1807 = 13×139
2×3×7×13×43×139 +1 = 3263443 は素数
2×3×7×13×43×139×3263443 +1 = 10650056950807 = 547×607×1033×31051
とすぐに合成数にぶち当たる．