■2^p−1の素因数(その2)

  [参]西来路・清水「初学者のための数論入門」講談社

にしたがって,2^p−1の素因数についてみていきます.

  2^11−1=23・89

  2^23−1=47・178481

  2^29−1=233・1103・2089

  2^67−1=193707721・761838257287(コール)

 素因数をpで割ると1余る素数になります.

  23÷11=2・・・1

  47÷23=2・・・1

  89÷11=8・・・1

  233÷29=8・・・1

  1103÷29=38・・・1

  2089÷29=72・・・1 

  178481÷23=7760・・・1

この性質は2^p−1が素数のときにも成り立ちます.

 さらに,素因数を8で割ると1または7余ります.

  23÷8=2・・・7

  47÷8=5・・・7

  89÷8=11・・・1

  233÷8=29・・・1

  1103÷8=137・・・7

  2089÷8=261・・・1 

  178481÷822310・・・1

この性質(第2補充則)は2^p−1がpが素数でなくても3以上の奇数であれば成り立ちます.

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

[Q]2^31−1は素数であるか?

[A]2^31−1=2147483647

  √2147483647=46340.95・・・3

 46340以下の素数が2147483647を割り切るかどうかを調べればよいのですが,そのような素数は4792個あります.ところが,

  性質:2^p−1の素因数をpで割ると1余る素数になる

  性質:2^n−1の素因数を8で割ると1または7余る素数になる

を用いると,31で割って1余る素数かつ8で割って1または7余る素数のみを調べればよいことがわかります.

 これは,すなわち,248で割って1または7余る素数(311,1301,・・・)になり,46340以下に84個あります.こうして,オイラーは

  2^31−1=2147483647(素数,オイラー)

を示しました.

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