12/08/19 15:26:01.36 ch7C5IyL0
[問] 素数が無限個存在することを示せ。
[証明] 背理法で示す。素数が有限個であって、小さい順に
a_1、a_2、a_3、…、a_n
のn個であると仮定する（つまり最大の素数をa_nとする）。
このとき、(a_1 * a_2 * a_3 * … * a_n) + 1という数は、
どの素数よりも大きいので素数でない。
一方、この数は、どの素数で割っても1余るので素数である。
矛盾をきたすので、はじめの仮定が誤りである。
すなわち、素数は無限個存在する。
----------------------------------------
という証明をいくつか見た記憶があるが
（どの参考書かどのサイトかは失念）、問題がないか。
上の証明では、nはどんな自然数であっても成り立たなくてはならない。
たとえば、n=6のときについて考える。
素数が2、3、5、7、11、13の6個しかないと仮定する。
このとき、2*3*5*7*11*13+1=30031 はどの素数よりも大きいので素数でない。
一方、30031はどの素数で割っても1余るので素数である。
と思ったら、30031 は 59*509 であるから素数ではない。
上の証明は、n=6で破綻している。
[質問]
「(a_1 * a_2 * a_3 * … * a_n) + 1 はどの素数 a_1、a_2、a_3、…、a_n で割っても1余るから素数」
という主張は、上の30031の例から誤っているはずだ。一見正しそうだが、なぜ間違いなのか。
反例を挙げれば確かに十分だが、うまく間違いの説明がつけられないか。
30031の例では、仮定した有限個の素数以外の素数59を出してくるのがまずいのだろうか。