カーマイケル数

カーマイケル数（カーマイケルすう、Carmichael number）とは、自身と互いに素である任意の底でフェルマーテストを通過する合成数である。アメリカの数学者ロバート・ダニエル・カーマイケル（Robert Daniel Carmichael）にちなんでこう呼ばれる。また、絶対擬素数 (absolute pseudoprimes) とも呼ばれる。

確率的素数判定法の一つであるフェルマーテストにおいて、素数ではないにもかかわらず確率的素数であると判定される数を擬素数と呼ぶ。擬素数であるかどうかはフェルマーテストの底ごとに定まり、ある底で擬素数であっても他の底で擬素数であるとは限らない。そのため、複数の底でフェルマーテストを行うことで、素数であることの信頼性を高めることができる。しかしながら、それ自身と互いに素である全ての底においてフェルマーテストを通過してしまう擬素数が存在し、それらはカーマイケル数と呼ばれる。すなわち、合成数 n がカーマイケル数であるとは、自身と互いに素である任意の自然数 a に対し、

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$

を満たすことをいう。

カーマイケル数は小さい方から

561, 1105, 1729, 2465, 2821, 6601, 8911, …（オンライン整数列大辞典の数列 A2997）

であり、無数に存在することが知られている。ただし、n が大きくなるにつれてカーマイケル数は極めてまれになっていく。たとえば、1 から 10²¹ の間には 20,138,200 個のカーマイケル数があり^[1]、これはおよそ 5*10¹³個にひとつの割合である。

カーマイケル数 n は、その全ての素因子 p に対して p − 1 が n − 1 を割り切るという特徴を持つ。例えば2821を例に取ると、

2821 = 7 × 13 × 31

2821 − 1 = 2820 = (7 − 1) × 470 = (13 − 1) × 235 = (31 − 1) × 94

である。逆に、この性質を持ち、平方因子を持たない合成数はカーマイケル数である。カーマイケル数は、少なくとも3個以上の異なる素数の積である。

フェルマーテストでは確率的素数と誤判定されるカーマイケル数であるが、フェルマーテストの改善版であるミラー-ラビン素数判定法では、ひとつの底に対する誤判定の確率は 1/4 以下となる。

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

• Weisstein, Eric W. "Carmichael Number". mathworld.wolfram.com (英語).