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

 2^340=1  (mod341)

341=11・13は2を底とする最小の擬素数である.

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

一方、561=3・11・17は最小の完全擬素数であって、561と互いの素などんなnに対しても

 n^560=1  (mod561)

すなわち、この余りはすべて1である。 ちなみにn=500のとき、n^560は1512桁になる。

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

561=3・11・17はカーマイケル数で,底を2〜aに取り替えても一切反応しません.

(証明)

 a^2=1 (mod3)

 a^10=1 (mod11)

 a^16=1 (mod17)

より,

 a^560=(a^2)^280=1 (mod3)

 a^560=(a^10)^56=1 (mod11)

 a^560=(a^16)^35=1 (mod17)

 つまり

  a^560=1 (mod561)

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