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

本文作成
 
(本文作成)
'''カーマイケル数'''は、自身と互いに素である任意の底で[[フェルマーの小定理#フェルマーテスト|フェルマーテスト]]を通過する擬素数である。'''強擬素数'''、'''絶対擬素数'''とも呼ばれる。
#REDIRECT [[フェルマーの小定理]]
 
==概要==
[[素数判定#確率的素数判定法|確率的素数判定法]]の一つである[[フェルマーの小定理#フェルマーテスト|フェルマーテスト]]において、素数でないのに確率的素数であると判定される数を'''擬素数'''と呼ぶ。この擬素数はフェルマーテストの底ごとに存在し、ある底で擬素数であっても他の底で擬素数であるとは限らない。そのためフェルマーテストでは複数の底で素数判定(本質的には合成数判定)を行うことで、高い確率で合成数ではない=確率的素数であると判定する。
{{main|フェルマーの小定理#フェルマーテスト}}
しかしながら、ほぼあらゆる底においてフェルマーテストを通過する擬素数がある。
 
それが強擬素数であり、カーマイケル数である。
 
カーマイケル数は、互いに素である任意の底でフェルマーテストを通過する擬素数であり、無限個存在することが知られている。
 
10000 以下のカーマイケル数は 561, 1105, 1729, 2465, 2821, 6601, 8911 である。
==特徴==
カーマイケル数は、カーマイケル数の全ての素因数mに関して(m-1)という値を(カーマイケル数-1)の因数に持つ特徴がある。
 
例えば2821を例に取ると、
 
: 2821 = 7 * 13 * 31
: 2821-1 = 2820 = (7-1) * 470 = (13-1) * 235 = (31-1) * 94
 
である。
 
フェルマーテストでは高い確率で誤判定(確率的素数と判定)されるカーマイケル数であるが、フェルマーテストの改善版である[[ラビン-ミラー素数判定法]]では誤判定の確率は通常通りとなる。
== 関連項目 ==
* [[素数]]
* [[素数判定]](確率的素数判定法)
#REDIRECT* [[フェルマーの小定理]](フェルマーテスト)
* [[ラビン-ミラー素数判定法]]
1,745

回編集