素数
素数とは、1とその数自身でしか割り切れない数です。素数の性質は、たとえば暗号によく使われています。
定義と例
素数とは、1とその数自身でしか割り切れない自然数のことです。ただし、1そのものは素数ではありません。いちばん小さい素数は2で、1と2で割り切れます。2は偶数である唯一の素数でもあります。ほかの偶数はどれも、1とその数自身のほかに2でも割り切れるので、2以外の素数はすべて奇数です。
はじめのいくつかの素数をならべると、次のようになります。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, 233, 239, 241, 251, 257, 263, 269, 271…
素数に関係する定理に、算術の基本定理があります。この定理によると、1より大きいどんな整数も、素数の積に分解できます。
素数かどうかを調べる
素数の性質
- 素数は無数にあります。証明は背理法の記事にあります。
- どんな整数 z>1 についても、区間 (z, 2z) には少なくとも1つの素数があります。例：z = 2 なら、区間は (2, 4) です。この区間にある整数は3だけで、3は素数です。z = 5 なら、区間は (5, 10) で、その中の整数は 6, 7, 8, 9 です。そのうち7は素数です。もっと大きい z でも同じです。
- メルセンヌ素数とは、2の累乗（指数は整数）より1小さい素数です。つまり、メルセンヌ素数 M は、z をある自然数として、M = 2z − 1 の形をしています。たとえば3は、22 − 1 = 3 なのでメルセンヌ素数です。7も、23 − 1 = 7 なのでメルセンヌ素数です。
- 知られている最大の素数は、メルセンヌ素数であることが多いです。たとえば2008年8月23日に、メルセンヌ素数 M43112609 が見つかりました。右下の添え字は指数 z を表します。つまり、これは素数 243112609 − 1 で、12,978,189 けたあり、当時知られていた最大の素数でした。
素数を含まない数の列
素数を1つも含まない連続する自然数の列は、いくらでも長いものを見つけることができます。たとえば k!+2, k!+3, …, k!+k という数の列は、連続する k − 1 個の合成数からなります（感嘆符は階乗を表します）。
たとえば k = 6 なら、720 + 2, 720 + 3, 720 + 4, 720 + 5, 720 + 6 という、連続する5つの合成数が得られます。これらの数は、順に2、3、4、5、6で割り切れます。6! = 720 は、これらの数の積 6! = 6 · 5 · 4 · 3 · 2 なので、どれでも割り切れるからです。720 が3で割り切れるなら、720 + 3 も3で割り切れるはずです。ほかの数も同じです。
フェルマーの小定理
どんな素数 p とどんな整数 z についても、zp − z は素数 p で割り切れます。
例：素数 p = 3 と整数 z = 4 をとります。43 − 4 を計算すると 60 になります。60/3 = 20 なので、3は60を割り切ります。これはフェルマーの小定理のとおりです。別の例として、p = 7, z = 10 とします。まず 107 − 10 = 9999990 を計算し、この数を7で割ります。9999990/7 = 1428570 となり、やはり割り切れます。
未解決問題
素数については、まだ（2011年の時点で）証明も反証もされていない有名な予想がたくさんあります。最も有名な2つを紹介します。
- 双子素数が無数にあるか：双子素数とは、数の組 (z, z + 2) で、どちらも素数であるものです。たとえば (3, 5) や (29, 31) です。問題は、双子素数が無数にあるかどうかです。無数にあると考えられていますが、証明はありません。
- リーマン予想：リーマンのゼータ関数の自明でない零点は、すべて実部が