【１】擬素数

　たとえば，

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

がｐが素数であるための必要条件を与えるが，残念ながら十分条件にはならない．

　カーマイケル数と呼ばれる多くの合成数が，

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

をパスしてしまうのだ．ａ＝３の場合，その最初のものはｎ＝５６１である．

　２００３年，アルフォード，グランヴィル，ポメランスがそのような数は無限個あることを証明した．彼等はｘを十分に大きい数とすると，ｘ以下のカーマイケル数は少なくともｘ^2/7個存在することを示したのである．

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