「カーマイケル数」の版間の差分
削除された内容 追加された内容
Maddestmagician (会話 | 投稿記録) 本文作成 |
急ぎ若干の手直し。「強擬素数」は別の概念 |
||
1行目: | 1行目: | ||
'''カーマイケル数'''は、自身と互いに素である任意の底で[[フェルマーの小定理#フェルマーテスト|フェルマーテスト]]を通過する |
'''カーマイケル数'''(カーマイケルすう、Carmichael number)とは、自身と[[互いに素]]である任意の底で[[フェルマーの小定理#フェルマーテスト|フェルマーテスト]]を通過する[[合成数]]である。'''絶対擬素数''' (absolute pseudoprimes) とも呼ばれる。 |
||
==概要== |
== 概要 == |
||
[[素数判定#確率的素数判定法|確率的素数判定法]]の一つである[[フェルマーの小定理#フェルマーテスト|フェルマーテスト]]において、素数でない |
[[素数判定#確率的素数判定法|確率的素数判定法]]の一つである[[フェルマーの小定理#フェルマーテスト|フェルマーテスト]]において、[[素数]]ではないにもかかわらず確率的素数であると判定される数を'''擬素数'''と呼ぶ。擬素数であるかどうかはフェルマーテストの底ごとに定まるため、ある底で擬素数であっても他の底で擬素数であるとは限らない。そのため、複数の底でフェルマーテストを行うことで、素数であることの信頼性を高めることができる。しかしながら、ほぼあらゆる底においてフェルマーテストを通過してしまう擬素数が存在し、それらはカーマイケル数と呼ばれる。すなわち、合成数 ''n'' がカーマイケル数であるとは、自身と互いに素である任意の自然数 ''a'' に対し、 |
||
:<math>a^{n-1} \equiv 1 \pmod n</math> |
|||
{{main|フェルマーの小定理#フェルマーテスト}} |
|||
を満たすことをいう。 |
|||
しかしながら、ほぼあらゆる底においてフェルマーテストを通過する擬素数がある。 |
|||
カーマイケル数は小さい方から |
|||
:561, 1105, 1729, 2465, 2821, 6601, 8911, …({{OEIS|A2997}}) |
|||
であり、無数に存在することが知られている。 |
|||
10000 以下のカーマイケル数は 561, 1105, 1729, 2465, 2821, 6601, 8911 である。 |
|||
⚫ | |||
カーマイケル数は、カーマイケル数の全ての素因数mに関して(m-1)という値を(カーマイケル数-1)の因数に持つ特徴がある。 |
|||
例えば2821を例に取ると、 |
|||
⚫ | |||
カーマイケル数 ''n'' は、その全ての素因子 ''p'' に対して ''p'' - 1 が ''n'' - 1 を割り切るという特徴を持つ。例えば2821を例に取ると、 |
|||
: 2821 = 7 * 13 * 31 |
: 2821 = 7 * 13 * 31 |
||
: 2821-1 = 2820 = (7-1) * 470 = (13-1) * 235 = (31-1) * 94 |
: 2821-1 = 2820 = (7-1) * 470 = (13-1) * 235 = (31-1) * 94 |
||
である。逆に、この性質を持ち、平方因子を持たない自然数はカーマイケル数である。カーマイケル数は、少なくとも3個以上の異なる素数の積である。 |
|||
⚫ | |||
である。 |
|||
⚫ | |||
== 関連項目 == |
== 関連項目 == |
||
* [[素数]] |
* [[素数]] |
||
* [[素数判定]](確率的素数判定法) |
* [[素数判定]](確率的素数判定法) |
||
* [[フェルマーの小定理]](フェルマーテスト) |
* [[フェルマーの小定理]](フェルマーテスト) |
||
* [[ |
* [[ミラー-ラビン素数判定法]] |
||
== 外部リンク == |
|||
*{{MathWorld|urlname=CarmichaelNumber|title=Carmichael Number}} |
|||
{{DEFAULTSORT:かあまいけるすう}} |
|||
[[Category:整数の類]] |
|||
[[Category:合同算術]] |
|||
[[Category:数学に関する記事]] |
|||
[[ca:Nombres de Carmichael]] |
|||
[[de:Carmichael-Zahl]] |
|||
[[en:Carmichael number]] |
|||
[[es:Número de Carmichael]] |
|||
[[eo:Nombro de Carmichael]] |
|||
[[fr:Nombre de Carmichael]] |
|||
[[ko:카마이클 수]] |
|||
[[it:Numero di Carmichael]] |
|||
[[pl:Liczby Carmichaela]] |
|||
[[pt:Número de Carmichael]] |
|||
[[ru:Числа Кармайкла]] |
|||
[[sl:Carmichaelovo število]] |
|||
[[fi:Carmichaelin luku]] |
|||
[[sv:Carmichaeltal]] |
|||
[[zh:卡邁克爾數]] |
2009年7月25日 (土) 12:07時点における版
カーマイケル数(カーマイケルすう、Carmichael number)とは、自身と互いに素である任意の底でフェルマーテストを通過する合成数である。絶対擬素数 (absolute pseudoprimes) とも呼ばれる。
概要
確率的素数判定法の一つであるフェルマーテストにおいて、素数ではないにもかかわらず確率的素数であると判定される数を擬素数と呼ぶ。擬素数であるかどうかはフェルマーテストの底ごとに定まるため、ある底で擬素数であっても他の底で擬素数であるとは限らない。そのため、複数の底でフェルマーテストを行うことで、素数であることの信頼性を高めることができる。しかしながら、ほぼあらゆる底においてフェルマーテストを通過してしまう擬素数が存在し、それらはカーマイケル数と呼ばれる。すなわち、合成数 n がカーマイケル数であるとは、自身と互いに素である任意の自然数 a に対し、
を満たすことをいう。
カーマイケル数は小さい方から
- 561, 1105, 1729, 2465, 2821, 6601, 8911, …(オンライン整数列大辞典の数列 A2997)
であり、無数に存在することが知られている。
特徴
カーマイケル数 n は、その全ての素因子 p に対して p - 1 が n - 1 を割り切るという特徴を持つ。例えば2821を例に取ると、
- 2821 = 7 * 13 * 31
- 2821-1 = 2820 = (7-1) * 470 = (13-1) * 235 = (31-1) * 94
である。逆に、この性質を持ち、平方因子を持たない自然数はカーマイケル数である。カーマイケル数は、少なくとも3個以上の異なる素数の積である。
フェルマーテストでは高い確率で確率的素数と誤判定されるカーマイケル数であるが、フェルマーテストの改善版であるミラー-ラビン素数判定法では、ひとつの底に対する誤判定の確率は 1/4 以下となる。
関連項目
- 素数
- 素数判定(確率的素数判定法)
- フェルマーの小定理(フェルマーテスト)
- ミラー-ラビン素数判定法
外部リンク
- Weisstein, Eric W. "Carmichael Number". mathworld.wolfram.com (英語).