３４１＝１１・１３は合成数であり，素数ではない．フェルマーの小定理の逆は成り立たない．フェルマー商

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

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

　２^340−１は３４１で割り切れる．３４１は２を底とする最小の擬素数である．

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

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

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

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

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

２^340 　（ｍｏｄ３４１）

を計算するにあたり、

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

が成り立つことは運がよかったといえるが、一般にはそんなに運がいいとは限らない。

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

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

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

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

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

　　２^85＝２^5（２^10）^8＝３２　　（ｍｏｄ３４１）

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

【１】強擬素数性検査

２^560＝１　　(mod 561)であるが、指数を半分にすると

２^280＝１　　(mod 561)

２^140＝６７≠-1　　(mod 561)→561は合成数であることが分かる。

２^2820＝１　　(mod 2821)であるが、指数を半分にすると

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

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