■素数であるか? (その54)

 フェルマーの小定理より,pが奇素数のとき2^p-1−1はpで割り切れる.

  p=3:2^2−1=3 (3で割り切れる)

  p=5:2^4−1=3 (5で割り切れる)

  p=7:2^6−1=63 (7で割り切れる)

  p=11:2^10−1=1027 (11で割り切れる)

 nが偶数のとき,2^n-1−1は奇数なので,nの倍数ではない.

 nが奇数の合成数のとき,

  n=9:2^8−1=255 (9で割り切れない)

  n=15:2^14−1=16383 (15で割り切れない)

  n=21:2^20−1=1048575 (21で割り切れない)

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

 フェルマーの小定理の逆は正しくない.

  n=341=11・31:2^340−1は341で割り切れる.

 このような擬素数は無限にある.

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

 つぎに,素数pに対して,2^p−1が素数(メルセンヌ素数)になる場合を検索してみる.

  2^2−1=3(素数)

  2^3−1=7(素数)

  2^5−1=31(素数)

  2^7−1=127(素数)

  2^11−1=23・89

  2^13−1=8191(素数)

  2^17−1=131071(素数)

  2^19−1=254287(素数)

  2^23−1=47・178481

  2^29−1=233・1103・2089

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

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

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