カーマイケル数
確率的素数判定法の一つであるフェルマーテストにおいて、素数ではないにもかかわらず確率的素数であると判定される数を擬素数と呼ぶ。擬素数であるかどうかはフェルマーテストの底ごとに定まり、ある底で擬素数であっても他の底で擬素数であるとは限らない。そのため、複数の底でフェルマーテストを行うことで、素数であることの信頼性を高めることができる。しかしながら、それ自身と互いに素である全ての底においてフェルマーテストを通過してしまう擬素数が存在し、それらはカーマイケル数と呼ばれる。すなわち、合成数 n がカーマイケル数であるとは、自身と互いに素である任意の自然数 a に対し、
a n − 1 ≡ 1 ( mod n ) {\displaystyle a^{n-1}\equiv 1{\pmod {n}}}
を満たすことをいう。
カーマイケル数は小さい方から
561, 1105, 1729, 2465, 2821, 6601, 8911, ...(オンライン整数列大辞典の数列 A2997)
であり、無数に存在することが知られている。ただし、n が大きくなるにつれてカーマイケル数は極めてまれになっていく。たとえば、1 から 10 の間には 20,138,200 個のカーマイケル数があり、これはおよそ 5*10個にひとつの割合である。