【１】擬素数

　たとえば，

　　ｎ｜２^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＝３２　　（ｍｏｄ３４１）

　なお，擬素数は素数の数よりも稀であるが，にもかかわらず，無限に存在する．

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