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

→‎概要: 「ほぼ」ではない
m (ロボットによる 追加: cs:Carmichaelovo číslo)
(→‎概要: 「ほぼ」ではない)
 
== 概要 ==
[[素数判定#確率的素数判定法|確率的素数判定法]]の一つである[[フェルマーの小定理#フェルマーテスト|フェルマーテスト]]において、[[素数]]ではないにもかかわらず確率的素数であると判定される数を'''擬素数'''と呼ぶ。擬素数であるかどうかはフェルマーテストの底ごとに定まり、ある底で擬素数であっても他の底で擬素数であるとは限らない。そのため、複数の底でフェルマーテストを行うことで、素数であることの信頼性を高めることができる。しかしながら、ほぼあらゆる可能な全ての底においてフェルマーテストを通過してしまう擬素数が存在し、それらはカーマイケル数と呼ばれる。すなわち、合成数 ''n'' がカーマイケル数であるとは、自身と互いに素である任意の自然数 ''a'' に対し、
:<math>a^{n-1} \equiv 1 \pmod n</math>
を満たすことをいう。