「カーマイケル数」の版間の差分

'''カーマイケル数'''（カーマイケルすう、Carmichael number）とは、自身と[[互いに素]]である任意の底で[[フェルマーの小定理#フェルマーテスト|フェルマーテスト]]を通過する擬素[[合成数]]である。'''強擬素数'''、'''絶対擬素数''' (absolute pseudoprimes) とも呼ばれる。

== 概要 ==

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

それが強擬素数であり、カーマイケル数である。は小さい方から

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

* [[ラビン-ミラー-ラビン素数判定法]]