■カーマイケル数は無数にある(その3)

341は底2であったが、すべての底b、(b、N)=1に対して、N|b^n-1-1となる合成数がカーマイケル数である。

最小のカーマイケル数は561=3・11・17である。

N=561に対してはφ(561)=320個のbに対して

  N|b^n-1-1

であることを調べなければならないのだろうか?

N=2821に対してはφ(2821)=2160個のbに対して

  N|b^n-1-1

であることを調べなければならないのだろうか?

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

われわれが必要とするものは、各pi-1がN-1=Π(pi-1)を割り切るような3つ以上の奇素数である。

561の場合、2,10,17は3・11・17-1=560を割り切る

2821の場合、6,12,30は7・13・31-1=2820を割り切る

これで十分なのである。

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

【1】強擬素数性検査

2^560=1  (mod 561)であるが、指数を半分にすると

2^280=1  (mod 561)

2^140=67≠-1  (mod 561)→561は合成数であることが分かる。

2^2820=1  (mod 2821)であるが、指数を半分にすると

2^1410=1520≠-1  (mod 2821)→2821は合成数であることが分かる。

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