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

 フェルマーの小定理より,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で割り切れる.

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

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