■メルセンヌ数(その2)
【2】メルセンヌ数の素数性判定
M13=8191 (素数)
M17=131071 (素数)
M19=524287 (素数)
M23=8388607 (非素数)
M29=536870911 (非素数)
M37=137438953471 (非素数)
に対して,
√8191=90.5・・・
√131071=362.0・・・
√524287=724.0・・・
√8388607=2896.3・・・
までのすべての素数が素因数であるかどうかを確認するのは電卓を用いても一苦労です.そこで,
命題:pを奇素数,qを素数とするとき,
2^q=1 (modp)ならば,p=1 (modq)
である
ことを用いることにします.すなわち,メルセンヌ数2^n−1が合成数であるならば,因数はあるkに対してkn+1型でというものす.
===================================
[1]M13=8191 (素数)
p≦90までの素数がM13の素因数でないことを示す.命題よりp=13n+1.n=1は偶数なので,素因数となりうるのはp=26n+1型と書ける.p=27,53,79が候補となるが,27は素数でなく,53,79は8191の約数でない.
[2]M17=131071 (素数)
p≦362までの素数がM17の素因数でないことを示す.p=34n+1型と書けるので,p=35,69,103,137,171,205,239,273,307,341が候補となる.35,69,171,205,273,341は素数でなく,103,137,239,307は131071の約数でない.
[3]M11=2^11−1 (非素数)
p=11n+1,n=1は偶数なので,素因数となりうるのは p=22n+1型と書ける.23は早速素数なので調べてみると
23=2・11+1
2^11−1=2047=23・89
[4]M23=2^23−1 (非素数)
p=23n+1,n=1は偶数なので,素因数となりうるのは p=46n+1型と書ける.47は早速素数なので調べてみると
47=2・23+1
2^23−1=8388607=47・178481
[5]M37=2^37−1 (非素数)
p=37n+1,n=1は偶数なので,p=74n+1型と書ける.
n=1:p=75(非素数)
n=2:p=149(素数)であるが,因数ではない.
n=3:p=223(素数)であり,因数でもある.
223=6・37+1
2^37−1=137438953471=223・61631877
===================================