数学

素数が無限に存在することの証明方法

素数が無限に存在することの証明

素数は無限に存在するのでしょうか?今回は素数が無限に存在することの証明についてお勉強していきましょう。

ペンちゃん
ペンちゃん
今回は素数が無限に存在することの証明についてお勉強しましょう!

素数とは

素数(Prime Number)とは

1と自分自身でしか割り切れない1より大きい整数

のことです。
小さいほうから50個の素数を並べると以下のようになります。

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229

素数は無限に存在するの?

素数は無限に存在するのでしょうか?次の定理が知られています。

素数は無限に存在する

証明方法

素数が無限個存在することの証明で一番有名なものはユークリッドの証明です。
実際の証明方法を見てみましょう。

証明

背理法で証明する。
素数がn個しかないとして、その有限個の素数を p1,p2,‥,pnとする。
p = p1p2‥pn + 1はpi (1≦i≦n)で割り切れないので素数となるが、
p > pi (1≦i≦n)なので最初に仮定した「素数がn個しかない」ことに矛盾する。
したがって、素数は無限個存在する。

まとめ

今回は素数についてお勉強しました。

素数
  • 素数とは1と自分自身でしか割り切れない1より大きい整数
  • 素数が無限個存在する
ペンちゃん
ペンちゃん
今回は素数が無限に存在することの証明についてお勉強したよ!