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

2004年3月18日 (木) 11:22時点における版

2009年7月25日 (土) 10:56時点における版

1行目:

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

#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* [[フェルマーの小定理]]（フェルマーテスト）

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