素数
＜素数＞
|
素数
|
|
素数とは約数が２つある自然数である。
|
つまり５の約数は１と５のみであるので５は素数。９の約数は１，３，９の３つなので素数ではありません。逆に約数が３つ以上ある自然数を合成数といいます。
＜素因数分解の一意性＞
|
素因数分解の一意性
|
|
全ての自然数は必ず１通りに素因数分解できる。 |
以下に１から１０００までの素数をあげます。（１００００までの素数表はこちら。）
＜素数表＞
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
547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659
661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809
811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941
947 953 967 971 977 983 991 997
１０００までの素数だけで１６８個もありました。なんの法則性もなさそうです。誰かn番目の素数をnで表せる人がいたら私にメールで教えてください。
ところで素数は無限にあるのでしょうか？その答えは紀元前の古代ギリシャのユークリッドがその著書、原論において、素数が無限であることを証明しています。ユークリッドの原論は聖書に次ぐベストセラーといわれています。その証明法を以下に記述します。
＜素数が無限にあることの背理法による証明＞
仮に素数が有限であったと仮定してその最大の素数をpとする。
２からpまでの素数を掛け合わせたものに１足した数qは、２からpまでのどの素数で割っても１余る、つまりqは素数である。しかしqはpより大きな素数である。これは仮定に反する。従って素数は無限に存在する。（証明終わり）
非常に単純明快な証明で誰でもすぐに納得がいきます。素数表があれば素数か合成数かの判別は容易ですが、手元にない場合はうまい方法があります。やはり古代ギリシャの”エラトステネスのふるい”が有名です。
＜エラトステネスのふるい＞
まず２以上の整数を必要なだけ書き出します。
２，３，４，５，６，７，８，９，１０，１１，１２，１３，１４，１５，１６，１７，１８，１９，２０，２１，２２，２３，２４，…
次に一番左の数２の、２を除く倍数を全て消していきます。
２，３，５，７，９，１１，１３，１５，１７，１９，２１，２３，…
さらに２の次の数３の、３を除く倍数を全て消していきます。
２，３，５，７，１１，１３，１７，１９，２３，…
以上のような操作を延々続けていけば最後に残るのは素数だけになります。
めんどくさいですね。他にいい方法はないものなんでしょうか？
＜ウィルソンの定理＞
|
ウィルソンの定理
|
|
pが素数なら (p-1)! ≡ -1(mod p) 、 また (p-1)! ≡ -1(mod p) ならpは素数。 |
この定理を使うとどうでしょうか？ちなみに ! は階乗とよみます。たとえば７の階乗は 7! = 7×6×5×4×3×2×1 = 5040 となります。これはあまり素数を発見する上で有用とはいえないような気がします。なぜなら、例えば16! = 20922789888000 となり、たかだか１７が素数かどうかの判定に１４桁もの数を扱わなくてはいけないということです。ちがうかな？
もう一つウィルソンの定理とよく似た定理を紹介します。
＜ライプニッツの定理＞
pが素数なら (p-2)! ≡ 1 (mod p)
ウィルソンの定理から容易に導けますねえ。
あと合同式を忘れた人、知らない人のために補足。
＜合同式＞
ａ≡ｂ (mod ｍ)
読み方： mを法としてaとbが合同
意味： a-bはmで割り切れる。
性質： a,b,c,dを整数、kを自然数とするとき、
１． ａ≡ｂ (mod ｍ)かつ ｃ≡ｄ (mod ｍ) なら
ａ＋ｃ≡ｂ＋ｄ(mod ｍ)
ａ−ｃ≡ｂ−ｄ (mod ｍ)
ａｃ≡ｂｄ (mod ｍ)
−ａ≡−ｂ (mod ｍ)
kａ≡kｂ (mod ｍ)
２． ｋａ≡ｋｂ (mod ｍ)のとき ｋとｍが互いに素ならば ａ≡ｂ (mod ｍ)
ところで素数が無限にあることはわかりました。では現在知られている最大の素数はいくらくらいなのでしょう？
２００６年９月の時点で
232582657-1
だそうです。大きすぎてどれくらいの数か想像できませんね。９８０万８３５８桁だそうです。
<メルセンヌ素数>
|
メルセンヌ素数
|
|
Mp=2p-1 の形をした素数をメルセンヌ素数といいます。 |
この形は必ず素数になるのでしょうか？pが素数ならMpは素数であると考えられていた時期もあったようです。しかし1536年に Hudalricus Regius により
211-1=23×89
となることを指摘されています。また１６０３年までにPietro Cataldiはpが１７と１９においてMpが素数となることを指摘していますが、pが２３、２９、３１、３７に関してもMpは素数であるとしています。これらは後にフェルマーが２３と３７の間違いを指摘し、オイラーが２９の間違いと３１は正しいことを指摘しています。ここで登場するのがフランスの修道士 Marin Mersenne（1588-1648）です。彼は
p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257
においてMpは素数であると予想しています(1644)。しかしこれ程までに大きな数字になるとそう簡単には確かめることは不可能ですね。実際オイラーがM31が素数であることを指摘したのはメルセンヌの発表から１００年以上経過した１７５０年でしたし、１８７６年にはLucas Test（後述）によりM127も素数であるとされています。また１８８３年にはPervouchineがM61を１９００年代にはPowersがM89,M107を素数であることを示しています。このようにして１６４４年にメルセンヌが２５７以下の素数に関するメルセンヌ数の表は１９４７年までに以下のように修正されました。
p =2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127
メルセンヌ数が出てきたところで非常に興味深い定理を紹介します。
＜（完全数に関する）オイラーの定理＞
|
（完全数に関する）オイラーの定理
|
|
Mp=2p-1が素数であるとき Pp=2p-1(2p-1) は完全数である。 |
ここで完全数の説明を行います。
＜完全数＞
”それ自身を除く約数の和が、元の数と等しくなる数”
のことです。具体的に例を挙げますと、６、２８、４９６などが完全数です。これらの約数は
６（１、２、３、６）
２８（１、２、４、７、１４、２８）
４９６（１、２、４、８、１６、３１、６２、１２４、２４８、４９６）
これら数はそれぞれ自身を除く約数の和としてあらわされます。
６＝１＋２＋３
２８＝１＋２＋４＋７＋１４
４９６＝１＋２＋４＋８＋１６＋３１＋６２＋１２４＋２４８
＜メルセンヌ素数表＞からp=２のとき P2=22-1(22-1)=6、p=3のとき P3=23-1(23-1)=28 で確かに完全数になっています。従いまして現在知られている最大の完全数は
P13466917=213466917-1(213466917-1)
という8107892桁の数です。
完全数が出てきたので友愛数についてもふれておきましょう。
＜友愛数＞
”それ自身を除く約数の和が、相手の数と等しくなる２つの数の組み合わせ。”
例えば２２０と２８４の約数を書き出すと
２２０ （１、２、４、５、１０、１１、２０、２２、４４、５５、１１０、２２０）
２８４ （１、２、４、７１、１４２、２８４）
220 = 1+2+4+71+142
284 = 1+2+4+5+10+11+20+22+44+55+110
となり自身を除く約数の和が、確かに相手の数に等しくなっています。このような組み合わせは
（２２０、２８４）、（１１８４、１２１０）、（２６２０、２９２４）
などが知られています。
次に１８７６年にLucasが 2127-1 を素数であることを発見した方法、Lucas Testについては以下を参照してください。
＜Lucas Test＞
pを奇素数とし、数列 Si (i=0,1,2,…) を次のように定める。
S1 = 4
Si+1 = Si2 - 2 (i = 0,1,2,…)
このとき Mp = 2p - 1 が
Sp-1 ≡ 0 (mod Mp)
なら Mp は素数である。
