1と自身でしか割り切れない数を素数といいます.
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,277,281,283,293,307,311,313,317,331, 337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449, 457,461,463,467,479,487,491,499,503,509,521,523,541...
どこまでも続いて行きそうですが,無限個存在するのでしょうか?
実はとても簡単に証明する事ができます.

証明

仮に素数が有限個しか存在しないとします.
すると,最大の素数Pが存在する事になります.
このPの階乗!Pに1を加えた数

!P+1

について考えてみます.
この数は2で割り切れるでしょうか?

 !P+1    = P*(P-1)*(P-2)*.....*3*2 +1

(!P+1)/2 = P*(P-1)*(P-2)*.....*3*2/2 +1/2
         = P*(P-1)*(P-2)*.....*3 + 1/2
         = !P/2 … 1

と1余ってしまい割り切れません.3ではどうでしょうか? 同様にして,

(!P+1)/3 = !P/3 … 1

となります.このように,!P+1は 2〜P全ての数で割り切れない事になり
!P+1を素因数分解すると,Pより大きな値が出てくる事になり
Pという最大の素数より大きな素数が存在する事になります.
また,その大きな素数をP'とした時,そのP'よりさらに大きな素数P''
が存在する事も同じ方法で証明できるので,素数が無限個存在するという事の証明になります.
簡単できれいな証明ですよね.

具体例

7より大きな素数が存在するか?

これを先ほどの方法で考えてみましょう.
まずは7の階乗を求めます.

!7= 7*6*5*4*3*2*1 = 5040

これに1を足した数,5041を素因数分解*1してみましょう.
まずは2で割り切れるか調べます.

5041 / 2 = (7*6*5*4*3*2*1 + 1) / 2
         = (7*6*5*4*3*2*1) / 2  + 1/2
         = (7*6*5*4*3  *1) + 1/2
         = 7*6*5*4*3*1  あまり 1

1余るので,5041を素因数分解しても2は出てこない事が分かります.
同様に3で割り切れるか調べると,

5041 / 3 = (7*6*5*4*3*2*1 + 1) / 3
         = (7*6*5*4*3*2*1) / 3  + 1/3
         = (7*6*5*4  *2*1) + 1/3
         = 7*6*5*4*2*1  あまり 1

3でも割り切れません.
これを続けていくと,

5041 / 2 = 7*6*5*4*3  *1  あまり 1
5041 / 3 = 7*6*5*4  *2*1  あまり 1
5041 / 4 = 7*6*5  *3*2*1  あまり 1
5041 / 5 = 7*6  *4*3*2*1  あまり 1
5041 / 6 = 7  *5*4*3*2*1  あまり 1
5041 / 7 =   6*5*4*3*2*1  あまり 1

という事が分かります.つまり,!7+1 (5041)は2〜7の数字では割り切れないという事です.
よって,!7+1 (5041)を素因数分解すると,7より大きな素数が出てくる事になります.
つまり,7より大きな素数が存在するという事です.
さらに,その7より大きな素数(何かは分からない)をPとした時に
!P+1 についても同じ事が言えるので,Pより大きな素数Qが存在する事も証明できて
さらにQより大きな素数も.... とすると,素数が無限に存在する事が分かります.

出現頻度

素数が無限個存在する事は分かりましたが,素数の出現頻度はどんな感じでしょうか?
感覚的には数が大きくなるにつれて,次に現れる素数まで間隔は広くなりそうですが...
Haskellでプログラムを書いて調べてみました.*2

--素数を求める(エラトステネスのふるい)
eratosthenesSieve (x:xs) =
    x: eratosthenesSieve [y|y<-xs, y `mod` x /=0]  --ふるいにかける
prime = eratosthenesSieve [2..]

--リストの隣り合った要素の差のリストを求める
listsDist (x:xs) = [head xs -x]++listsDist xs

試しに素数を5000個求めてみます.

take 5000 (listsDist prime)

結果はこの様になりました.

この結果を使い,素数(prime)と隣の素数との差(dist)をグラフ化してみました.

distprime.png

意外な事に,素数同士の間隔は5000番目の素数までを見ても,あまり広がりません.
その為,素数のグラフも直線に近い形*3をしています.面白いですね.

10万個の素数

10万番目の素数(1299709)まで求めてみました.約130万です.
という事は10万番目の素数までは平均13ごとに一つ素数が存在する事になります.

10万番目までの素数fileprimes100000.txt
隣り合う素数の間隔filedists100000.txt
今回もグラフ化してみました.解像度が高めです.

distsgraph100000.png

クリックすると大きく表示します.

リンク

  • How to prove that all odd numbers are prime
    「全ての奇数が素数である事をどうやって証明しますか?」.この問いに様々な分野の方が解答しています.
    色々な人の証明を見てみましょう.面白いです.

コメント


お名前:

*1 どの素数をかけると5041になるか調べる
*2 Haskellだとわずか3行・・・びっくり
*3 若干下にへこんでますが
添付ファイル: fileprimes100000.txt 2854件 [詳細] filedists100000.txt 1246件 [詳細] filedistsgraph100000.png 1544件 [詳細] filedistprime.png 1434件 [詳細] fileprimedists.txt 1309件 [詳細]