■素数定理とエラトステネスのふるい(その33)

 メルセンヌ数2^n−1が合成数であるならば,因数はあるkに対してkn+1である.

  2^11−1=2047=23・89→23=2・11+1

  2^23−1=8388607=47・178481→47=2・23+1

  2^37−1=137438953471=223・61631877→ 223=6・37+1

===================================

[1]2^11−1

 √2047=45.2・・・

 そこで,命題:pを奇素数,qを素数とする

  2^q=1  (modp)

ならば,p=1  (modq)であるを用いると,素因数となりうるのは p=22n+1型と書ける.23は早速素数なので調べてみると

  2047=23・89

===================================

[2]2^37−1

 p=37n+1、n=1は偶数なので,p=74n+1型と書ける.

  n=1:p=75(非素数)

  n=2:p=149(素数)であるが,因数ではない.

  n=3:p=223(素数)であり,因数でもある.

  137438953471=223・61631877

===================================