カーマイケル数のソースを表示

'''カーマイケル数'''（カーマイケルすう、Carmichael number）とは、自身と[[互いに素 (整数論)|互いに素]]である任意の[[底]]で[[フェルマーの小定理#フェルマーテスト|フェルマーテスト]]を通過する[[合成数]]である。アメリカの数学者[[ロバート・ダニエル・カーマイケル]]（[[:en:Robert Daniel Carmichael|Robert Daniel Carmichael]]）にちなんでこう呼ばれる。また、'''絶対擬素数''' (absolute pseudoprimes) とも呼ばれる。

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

カーマイケル数は小さい方から
:[[561]], 1105, [[1729]], 2465, 2821, 6601, 8911, …（{{OEIS|A2997}}）
であり、無数に存在することが知られている。ただし、''n'' が大きくなるにつれてカーマイケル数は極めてまれになっていく。たとえば、1 から 10<sup>21</sup> の間には 20,138,200 個のカーマイケル数があり<ref name="Pinch2007">Richard Pinch, [http://s369624816.websitehome.co.uk/rgep/p82.pdf "The Carmichael numbers up to 10<sup>21</sup>"], May 2007.</ref>、これはおよそ 5*10<sup>13</sup>個にひとつの割合である。

== 特徴 ==
カーマイケル数 ''n'' は、その全ての素因子 ''p'' に対して ''p'' &minus; 1 が ''n'' &minus; 1 を割り切るという特徴を持つ。例えば2821を例に取ると、
: 2821 = 7 &times; 13 &times; 31
: 2821 &minus; 1 = 2820 = (7 &minus; 1) &times; 470 = (13 &minus; 1) &times; 235 = (31 &minus; 1) &times; 94
である。逆に、この性質を持ち、平方因子を持たない合成数はカーマイケル数である。カーマイケル数は、少なくとも3個以上の異なる素数の積である。

フェルマーテストでは確率的素数と誤判定されるカーマイケル数であるが、フェルマーテストの改善版である[[ミラー-ラビン素数判定法]]では、ひとつの底に対する誤判定の確率は 1/4 以下となる。

==脚注==
{{reflist}}

== 関連項目 ==
* [[素数]]
* [[素数判定]]（確率的素数判定法）
* [[フェルマーの小定理]]（カーマイケルの定理、フェルマーテスト）
* [[ミラー-ラビン素数判定法]]

== 外部リンク ==
*{{MathWorld|urlname=CarmichaelNumber|title=Carmichael Number}}

{{DEFAULTSORT:かあまいけるすう}}
[[Category:擬素数]]
[[Category:合同算術]]
[[Category:数学に関する記事]]