■素数性判定(その3)

【5】擬素数の望ましくない性質

ところが,フェルマーの小定理の逆は成り立たちません.

[1]擬素数

   2^n-1=1   (mod n)

が成り立つ合成数nのこと.最小の擬素数は341.

   2^340=1   (mod 341)

ですが,341は素数ではありません

  341=11・31(合成数)

次に,底3を使えば,

   3^340=56   (mod 341) これは341が合成数である証拠です.

[2]完全擬素数(カーマイケル数)

 341は2を底とする最小の擬素数でしたが,どんな底に対しても,nと互いに素であるすべてのaに対して

   a^n=a   (mod n)

が成り立つ合成数nのこと.最小のカーマイケル数は561.

1912年,カーマイケルは,561が完全擬素数であることを示しました.b=2からb=559まで

  b^561=b   (mod 561)

が成り立つことを確かめたのです.

561=3・11・17

b^561−bが561で割り切れることを示すためには,3,11,17で割り切れることを示さなければならなりません.

  b^561=b  (mod 3)

  b^561=b  (mod 11)

  b^561=b  (mod 17)

ここでは,

  b^561=b  (mod 17)

を示します.17がbを割り切らないとき,フェルマーの小定理より,

  b^16=1  (mod 17)

561=35・16+1より,

  b^561=(b^16)^35・b=b  (mod 17)

となる.同様に

  561=280・2+1

  561=56・10+1

より,

  b^561=b  (mod 3)

  b^561=b  (mod 11)

も示すことができます.

[3]コーセルトの定理

大きな数nが,2とn−2の間の底に関して,擬素数であるかどうかをしらみつぶしに調べることは大変な作業ですが,コーセルトの定理を使えば証明はかなり簡単になります.

 奇数n=p・q・r・・・がカーマイケル数であるのは,素因数pに対して

[1]p^2はnを割り切らない

[2]p−1はn−1を割り切る

が成り立つとき,かつ,そのときに限る(コーセルトの定理).

したがって,

  561=3・11・17

がカーマイケル数であることを示すには,

[1]561≠0  (mod9)

[2]561≠0  (mod121)

[3]561≠0  (mod289)

[4]560=0  (mod2)

[5]560=0  (mod10)

[6]560=0  (mod16)

であることがいえればよいことになる.

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