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

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

［１］擬素数

　　　２^n-1＝１　　　（ｍｏｄ　ｎ）

が成り立つ合成数ｎのこと．最小の擬素数は３４１．

　　　２^340＝１　　　（ｍｏｄ　３４１）

ですが，３４１は素数ではありません

　　３４１＝１１・３１（合成数）

次に，底３を使えば，

　　　３^340＝５６　　　（ｍｏｄ　３４１） これは３４１が合成数である証拠です．

［２］完全擬素数（カーマイケル数）

　３４１は２を底とする最小の擬素数でしたが，どんな底に対しても，ｎと互いに素であるすべてのａに対して

　　　ａ^n＝ａ　　　（ｍｏｄ　ｎ）

が成り立つ合成数ｎのこと．最小のカーマイケル数は５６１．

１９１２年，カーマイケルは，５６１が完全擬素数であることを示しました．ｂ＝２からｂ＝５５９まで

　　ｂ^561＝ｂ　　　（ｍｏｄ　５６１）

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

５６１＝３・１１・１７

ｂ^561−ｂが５６１で割り切れることを示すためには，３，１１，１７で割り切れることを示さなければならなりません．

　　ｂ^561＝ｂ　　（ｍｏｄ　３）

　　ｂ^561＝ｂ　　（ｍｏｄ　１１）

　　ｂ^561＝ｂ　　（ｍｏｄ　１７）

ここでは，

　　ｂ^561＝ｂ　　（ｍｏｄ　１７）

を示します．１７がｂを割り切らないとき，フェルマーの小定理より，

　　ｂ^16＝１　　（ｍｏｄ　１７）

５６１＝３５・１６＋１より，

　　ｂ^561＝（ｂ^16）^35・ｂ＝ｂ　　（ｍｏｄ　１７）

となる．同様に

　　５６１＝２８０・２＋１

　　５６１＝５６・１０＋１

より，

　　ｂ^561＝ｂ　　（ｍｏｄ　３）

　　ｂ^561＝ｂ　　（ｍｏｄ　１１）

も示すことができます．

［３］コーセルトの定理

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

　奇数ｎ＝ｐ・ｑ・ｒ・・・がカーマイケル数であるのは，素因数ｐに対して

［１］ｐ^2はｎを割り切らない

［２］ｐ−１はｎ−１を割り切る

が成り立つとき，かつ，そのときに限る（コーセルトの定理）．

したがって，

　　５６１＝３・１１・１７

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

［１］５６１≠０　　（ｍｏｄ９）

［２］５６１≠０　　（ｍｏｄ１２１）

［３］５６１≠０　　（ｍｏｄ２８９）

［４］５６０＝０　　（ｍｏｄ２）

［５］５６０＝０　　（ｍｏｄ１０）

［６］５６０＝０　　（ｍｏｄ１６）

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

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝