カーマイケル数

カーマイケル数について

カーマイケル数とは、特定の性質を持つ合成数のことで、すべての底が自身と互いに素であるとき、フェルマーテストをクリアする数を指します。この名前は、数学者ロバート・ダニエル・カーマイケルに由来し、時には絶対擬素数とも呼ばれることがあります。カーマイケル数は数学的な興味をそそる存在であり、数論において重要な役割を果たします。

概要

カーマイケル数は、確率的素数判定の手法であるフェルマーテストにおいて、合成数であるにも関わらず、誤って素数として判定される特異な数です。擬素数として知られるこのような数は、特定の自然数の底に対して判定されますが、違う底に対して同様の特性を持つとは限りません。したがって、数を素数と確信するためには、複数の底でフェルマーテストを行うことが推奨されます。

しかし、カーマイケル数はあらゆる底でフェルマーテストを通過するため、特に注意が必要です。例えば、合成数 n がカーマイケル数である場合、すべての自然数 a に対して次の式が成り立ちます：

$$
a^{n-1} ≡ 1 ext{ (mod n)}$$

この性質により、カーマイケル数は合成数でありながら、素数に似た振る舞いを見せます。

カーマイケル数の例

カーマイケル数は無限に存在し、最も小さな数は561, 1105, 1729, 2465, 2821, 6601, 8911などです。興味深いことに、n が大きくなるにつれてカーマイケル数は非常に稀になります。具体的には、1から1021の間には約20,138,200の合成数が存在しますが、その中でカーマイケル数はごくわずか、つまり約5×10^13に1つの割合で発見されます。

特徴

カーマイケル数は、各素因子 p において次の特性を持っています：

• - その全ての素因子 p に対し、p - 1 が n - 1 を割り切ります。

例えば、2821を考えてみましょう。

$$
2821 = 7 × 13 × 31
$$

次に、2821 - 1 は2820で、次のように表せます：

$$
2820 = (7 - 1) × 470 = (13 - 1) × 235 = (31 - 1) × 94
$$

このように、全ての素因子においてその特性が成り立つため、2821はカーマイケル数であると言えます。カーマイケル数は、必ず少なくとも3つの異なる素数の積で構成されています。

フェルマーテストと確率的素数判定

カーマイケル数はフェルマーテストにおいて誤った結果を示すため、特に注意が必要です。しかし、改良された手法、ミラー-ラビン素数判定法を使用することで、誤判定の確率を1/4以下に抑えることが可能です。このため、カーマイケル数に出会ったときは、他の判定法を使うことでその正確な性質を掴むことが可能です。

まとめ

カーマイケル数は、合成数でありながら素数判定で誤って素数と見なされる特異な性質を持っています。この数の研究は、確率的素数判定における興味深い問題を提起し、数学のさらなる探求を促している存在です。

もう一度検索