フェルマーの小定理の逆は成り立たない．フェルマー商

　　（２^(p-1)−１）／ｐ

が整数になる（２^(p-1)−１がｐで割り切れる）のに，ｐが素数でない場合，ｐを擬素数（プーレ数）という．

　２^340−１は３４１で割り切れるのみ，３４１＝１１・１３は合成数であり，素数ではない．３４１は２を底とする最小の擬素数である．

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

【１】擬素数

　たとえば，

　　ｎ｜２^n−２

において，ｎ＝５のとき２^5−２＝３０は５で割り切れるが，ｎ＝１５のとき２^15−２＝３２７６６は１５で割り切れない．

　フェルマーの定理「ａが素数ｐと公約数をもたないならば，ａ^p-1−１はｐで割り切れる」は，記号

　　（ａ，ｐ）＝１→ｐ｜ａ^p-1−１

を用いて表される．

　しかし，フェルマーの定理の逆は真ではない．ｎ＝３４１＝１１・３１のとき，２^341−２は３４１で割り切れる．ｎが素数のときかつそのときに限って

　　ｎ｜２^n−２，２^n＝２　　（ｍｏｄｎ）

は「・・・のとき」は正しいが，「かつそのときに限って」は誤っている．

　ｎが奇数のとき

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

と書いてもよい．

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

であることを実際に確かめてみよう．

　　２^10＝１０２４＝１　　（ｍｏｄ３４１）

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

　３４１は２を底とする擬素数と呼ばれる．もっと一般に

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

が成り立つ奇数の合成数であると定義される．

　３４１は２を底とする最小の擬素数であるから，逆にいえば，ｎが３４１より小さい奇数のとき，ｎが素数でないならば２^n−２はｎで割り切れないことになる．

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

であったが，２^170　　（ｍｏｄ３４１）は＋１か−１か？

　　２^170＝（２^10）^17＝１　　（ｍｏｄ３４１）

それでは，２^85　　（ｍｏｄ３４１）は？

　　２^170＝２^5（２^10）^17＝３２　　（ｍｏｄ３４１）

　６４５は２を底とする２番目の擬素数．１１０５，１３８７，１９０５，・・・と続く．なお，擬素数は素数の数よりも稀であるが，にもかかわらず，無限に存在する．

　１６１０３８０は２を底とする偶数の擬素数，２番目は２１５３２６．偶数の擬素数は無限に存在することが証明されている．

　９１は３を底とする最小の擬素数．

　１５は４を底とする最小の擬素数．２番目は２１７．

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

【２】完全擬素数（カーマイケル数）

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

　　ａ^p−ａ

がｐで割り切れるとき，ｐを完全擬素数（カーマイケル数）という．

　５６１は最小の完全擬素数であて，以下，

　　１１０５，１７２９，２４６５，２８２１，６６０１，８９１１，１０５８５，・・・

と続く．無限に存在することが証明されている．

　どのカーマイケル数も少なくとも３つの素因数を含む．

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

【３】超プーレ数

　どの約数ｄに対しても，２^d−２がｄで割り切れる数を超プーレ数という．２０４７は超プーレ数である．超プーレ数はすべて奇数である．

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