素数の定義と素数が無限に多く存在することの証明

スポンサーリンク
素数の定義}  2個の正の約数(1と自分自身)をもつ自然数  [\,背理法による証明\,]   素数が有限個であると仮定}し,\ そのすべて}を小さい順に$p_1,\ p_2,\ ・・・,\ p_n\ とおく.$   そして,\ $「\,N=p_1p_2・\,・・・\,・ p_n+1}\,」$という数を考えると,\ 明らかに$N>p_n$である.   $N$は$p_1,\ ・・・,\ p_n$のいずれでも割り切れないから素数である.   $N>p_n$より,\ $N$は$p_1,\ ・・・,\ p_n$とは異なる素数である.   これは,\ $p_1,\ ・・・,\ p_n$がすべての素数であることに矛盾}する.   よって,\ 素数は無限に多く存在する.{ユークリッドによる証明(紀元前)\,]   任意の異なる$n$個の素数を小さい順に$p_1,\ p_2,\ ・・・,\ p_n$とする.   そして,\ $「\,N=p_1p_2・\,・・・\,・ p_n+1}\,」$という数を考えると,\ 明らかに$N>p_n$である.   $N$が素数}ならば,\ \ $N>p_n$より,\ $p_1,\ ・・・,\ p_n$とは異なる素数$N$が得られた}ことになる.   $N$が合成数}ならば,\ \ $N$を割り切る素数が存在するはずである.   ところが,\ $N$は$p_1,\ ・・・,\ p_n$のいずれでも割り切れない.   よって,\ $N$を割り切るような$p_1,\ ・・・,\ p_n$とは異なる素数が存在する.}   どちらにせよ$p_1,\ ・・・,\ p_n$とは異なる素数が存在するから,\ 素数は無限に多く存在する.} 1は1自身の1個しか正の約数をもたないから素数(prime\ number})ではない. 素数が無限に多く存在することの証明は受験で問われることはほとんどなく,\ 重要度は低い. しかし,\ 数学を学習する以上,\ 常識的な知識としてもっておきたい. 受験生にとって一般的な背理法による間接証明とユークリッドによる最古の証明を示した. 背理法による証明をみて,\ N=(素数の積)+1が必ず素数になると誤解}してしまう人が多い. Nは素数というのは,\ 素数が有限個という誤った仮定から導かれた誤った結果である. 実際には,\ Nは素数になる場合もあれば合成数になる場合もある.} 例えば,\ N=2・3・5+1=31=(素数),\ \ N=2・3・5・7・11・13+1=59×509\ である. Nが素数になる場合と合成数になる場合に分けて考えるのがユークリッドによる証明である. Nが素数にしても合成数にしても,\ 新たな素数が必ず存在することを示すことができる. Nは有限個の素数を元に新たな素数の存在を示唆する式}というわけである. つまり,\ 有限個の素数でNを作ると,\ N自体か,\ あるいはその約数として新たな素数が見つかる. 5以上の素数は,\ ある自然数$n$を用いて$6n-1$または$6n+1$の形で表されること \ \ を示せ. (2)\ \ $N$を自然数とする.\ $6N-1$は,\ $6n-1\ (nは自然数)$の形で表される素数を約数に \ \ もつことを示せ. (3)\ \ $6n-1$の形で表される素数は無限に多く存在することを示せ.    [\,千葉大\,]  (1)\ \ 5以上のすべての自然数は,\ 次のいずれかの形で表すことができる. $6n-1,\ 6n,\ 6n+1,\ 6n+2,\ 6n+3,\ 6n+4 (n:自然数)}$} このうち,\ $6n,\ 6n+2=2(3n+1),\ 6n+4=2(3n+2)$は2の倍数である. また,\ $6n+3=3(2n+1)$は3の倍数である. よって,\ 5以上の素数は$6n-1}$または$6n+1}$の形で表される.} \\  (2)\ \ $6N-1$は2の倍数でも3の倍数でもない5以上の自然数である. よって,\ $6N-1$がもつ素因数はすべて5以上の素数である. (1)より,\ $6N-1$がもつ素因数はすべて$6n-1$または$6n+1$の形で表される. ここで,\ $a,\ b$を自然数とすると $(6a+1)(6b+1)=6(6ab+a+b)+1=6N+1$ よって,\ $6n+1$の形の素数の積は必ず$6N+1$の形の整数}となる. ゆえに,\ $6N-1}$は$6n-1}$の形で表される素数を少なくとも1つ約数にもつ.} \\  (3)\ \ $6n-1$の形の素数が有限個であると仮定}し,\ そのすべてを$p_1,\ p_2,\ ・・・,\ p_n$とおく. そして,\ $「\,P=6p_1p_2・\,・・・\,・ p_n-1}\,」$という数を考える. $Pは6N-1$の形をしているから,\ (2)より$6n-1$の形の素数を約数にもつはずである. ところが,\ $Pはp_1,\ ・・・,\ p_n$のいずれでも割り切れないから,\ これは矛盾}である. よって,\ $6n-1}$の形で表される素数は無限に多く存在する.} 4n±1型,\ 6n±1型の素数が無限に多く存在するという有名事実がある. 本問は,\ 6n-1型の素数が無限に多く存在することの証明である. 誘導があっても,\ 初見で完答するのは難しいだろう. 4n-1型についても同様に証明できるが,\ 4n+1,\ 6n+1型には同様の手法は通用しない. 受験における重要度は低いが,\ 過去に出題歴があるので取り上げておく. (1)\ \ 実際に書き出してみると,\ 確かにどの素数も6n-1または6n+1の形であるように思える. \ \  6n-1:5,\ 11,\ 17,\ 23,\ 29,\ 41,\ ・・・・・・   6n+1:7,\ 13,\ 19,\ 31,\ 37,\ 43,\ ・・・・・・ \ \ この事実は,\ 一見不思議に感じられるかもしれない. \ \ しかし,\ その本質は5以上の素数は2の倍数でも3の倍数でもない}というだけの話である. \ \ 自然数から2の倍数と3の倍数を除外すると,\ 6で割ると1または5余る数のみが残る. (2)\ \ 6N-1=6(N-1)+5は6で割ると5余る数であるから,\ 2の倍数でも3の倍数でもない. \ \ 示すべきは,\ 6n-1型の素数を少なくとも1つ約数にもつことである. \ \ 「少なくとも~」であるから,\ 背理法}による証明が有効である. \ \ つまり,\ すべての素因数が6n+1型の素数と仮定して矛盾を導けばよい. (3)\ \ 素数が無限に多く存在することの証明と同様の設定で証明できる.