■素数と素因数分解(その4)

 M23=8388607       (非素数)

 M29=536870911     (非素数)

 M37=137438953471  (非素数)

 フェルマーはM17は非素数であることを発見しているが,ここではM23=8388607の非素数性を判定してみよう.

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

 √8388607=2896.3・・・

までの範囲の素数を確認するのは電卓を用いても一苦労である.しかし,この数が素数卯でないことなら証明できるかもしれない.

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

  2^q=1  (modp)

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

  8388607=47・178481  (QED)

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