カーマイケル数

カーマイケル数は、自身と互いに素である任意の底でフェルマーテストを通過する擬素数である。強擬素数、絶対擬素数とも呼ばれる。

概要

確率的素数判定法の一つであるフェルマーテストにおいて、素数でないのに確率的素数であると判定される数を擬素数と呼ぶ。この擬素数はフェルマーテストの底ごとに存在し、ある底で擬素数であっても他の底で擬素数であるとは限らない。そのためフェルマーテストでは複数の底で素数判定（本質的には合成数判定）を行うことで、高い確率で合成数ではない＝確率的素数であると判定する。

詳細は「フェルマーの小定理#フェルマーテスト」を参照

しかしながら、ほぼあらゆる底においてフェルマーテストを通過する擬素数がある。

それが強擬素数であり、カーマイケル数である。

カーマイケル数は、互いに素である任意の底でフェルマーテストを通過する擬素数であり、無限個存在することが知られている。

10000 以下のカーマイケル数は 561, 1105, 1729, 2465, 2821, 6601, 8911 である。

特徴

カーマイケル数は、カーマイケル数の全ての素因数mに関して(m-1)という値を(カーマイケル数-1)の因数に持つ特徴がある。

例えば2821を例に取ると、

2821 = 7 * 13 * 31

2821-1 = 2820 = (7-1) * 470 = (13-1) * 235 = (31-1) * 94

である。

フェルマーテストでは高い確率で誤判定（確率的素数と判定）されるカーマイケル数であるが、フェルマーテストの改善版であるラビン-ミラー素数判定法では誤判定の確率は通常通りとなる。

関連項目

• 素数
• 素数判定（確率的素数判定法）
• フェルマーの小定理（フェルマーテスト）
• ラビン-ミラー素数判定法