カーマイケル数：性質、コルセルトの判定法、例と素数判定への影響

主要な性質と特徴付け

カーマイケル数には、コルセルトに帰される判定法による簡潔な代数的記述がある。合成数 n がカーマイケル数であるための必要十分条件は、n が平方因子をもたないこと、すなわちある素数の平方が n を割り切らないこと、かつ n を割り切る各素数 p について p − 1 が n − 1 を割り切ることである。この整除条件により、n と互いに素なすべての b に対して bn−1 ≡ 1 (mod n) が成り立つ理由が説明される。各素因数を法とする任意の単元の位数は n − 1 を割り切り、中国剰余定理によって局所的な合同式が大域的な合同式へと統合される。

この判定法から、いくつかの直接的な帰結が得られる。すべてのカーマイケル数は奇数であり、平方因子をもたず、少なくとも3個の相異なる素因数をもつ。これらの制約によって、カーマイケル数は大多数の合成整数と区別される。

例と小さな場合

最小で最もよく挙げられる例は 561 = 3・11・17 であり、このような数の研究の初期に確認された。561 と互いに素なすべての b について、b560 ≡ 1 (mod 561) が成立する。別の標準的な例は 1105 = 5・13・17 である。これらの数は、コルセルトの整除条件がどのように成立するかを明示している。たとえば 561 では、各素因数 p に対する p − 1 が 560 を割り切る。小さなカーマイケル数の一覧は、教育や素数判定アルゴリズムの堅牢性の試験に用いられる。さらなる例は、素数および擬素数に関する文献の計算表や参考資料に見いだせる。

歴史と発展

この名称は、20世紀初頭にこの種の合成数を研究し、561 を有益な例として注目させたロバート・カーマイケルに由来する。検証を実際的なものにする構造的判定法はコルセルトによるもので、後にフェルマー擬素数の議論において広く知られるようになった。数十年にわたり、カーマイケル数はまれな珍しい対象のように見えた。しかし重要な進展として、カーマイケル数が無限に存在することが証明され、単純な素数判定に対する孤立した反例以上のものであることが明らかになった。その定義の基礎にある合同の考え方については、剰余演算および合同式に関する解説を参照できる。

用途、意義、およびアルゴリズムへの影響

カーマイケル数は、フェルマーの小定理だけに基づく単純な素数判定の弱点を明らかにするため、計算数論において重要である。ある底 b に対して bn−1 ≡ 1 (mod n) を満たす数 n は、底 b に関するフェルマー擬素数と呼ばれる。カーマイケル数は、n と互いに素なすべての底に関するフェルマー擬素数である。このため、このような普遍的擬素数に惑わされないよう、ミラー–ラビン判定法や決定的な AKS アルゴリズムのように追加の構造に依拠する、より強力な確率的・決定的判定法が開発・採用されてきた。したがって実用的な素数判定では、判定の信頼性を評価する際に、カーマイケル数を有益な最悪例として扱う。

注目すべき区別と事実

• 平方因子をもたず複数の因数をもつ：すべてのカーマイケル数は平方因子をもたず、少なくとも3個の相異なる素因数をもつ。したがって素数でも素数べきでもない。
• 無限性：カーマイケル数が無限に存在することは定理として知られている。この結果は、その希少性に関する従来の見方を変え、解析的数論における密度評価にも影響を及ぼす。
• 他の擬素数との関係：カーマイケル数は、互いに素なすべての底に対してフェルマー判定を欺くことから、絶対フェルマー擬素数または普遍フェルマー擬素数と呼ばれることがある。ただし、オイラー判定や強擬素数判定など、より強い基準によって検出できる場合が多い。
• 計算上の役割：コルセルトの判定法のような性質を知ることは、カーマイケル数の構成と検証、および偽陽性を避ける素数判定ルーチンの設計に役立つ。

さらに学びたい読者にとっては、剰余演算と素数判定の入門書が理解しやすい入口となる。また、計算数論の資料には、カーマイケル数および関連する擬素数を識別するための表とアルゴリズムが収録されている。より広い文脈については、合成数、正整数、フェルマーの小定理に関する解説も参照されたい。