導入
数論では、カーマイケル数は次の性質を満たす正の合成整数nです。
- 任意の整数aについて、 n はa n − aの約数です
概要
フェルマーの小定理は、素数には次の性質があると述べています。
数が大きくなり、カーマイケル数が希少になるにつれて、その大多数により、フェルマーの素数性テストは、ソロベイ・ストラッセンの素数性テストのような他の素数性テストと比較してほとんど役に立たなくなります。たとえば、 646 番目のカーマイケル数は 993,905,641 で、1 から 10 15までのカーマイケル数は 105,212 個あります。
カーマイケル数の特徴付けは、1899 年にコーセルトの定理によって与えられました。
定理(Korselt 1899): 合成正の整数nは、 n を割る素数の二乗が存在しない場合 ( n はquadratfrei (二乗なし)であると言います)、およびnの各素約数pについて、数pである場合に限り、カーマイケル数になります。 − 1 はn − 1 を除算します。
この定理から、すべてのカーマイケル数は少なくとも 3 つの異なる奇数素数の積であることがわかります。
コーセルトはこれらの特性を最初に観察しましたが、カーマイケル数の例を見つけることができませんでした。 1910 年にロバート ダニエル カーマイケルはこれらの数字の中で最も小さい 561 を発見し、これらは彼の名誉を讃えて命名されました。
このカーマイケル数 561 は、コルセルトの定理で検証できます。実際、561 = 3 · 11 · 17 は平方素数で割り切れず、3 – 1 = 2、11 – 1 = 10、17 – 1 = 16 はすべて 560 の約数です。
最初のカーマイケル数は次のとおりです。
- 561 = 3 · 11 · 17
- 1105 = 5 · 13 · 17
- 1729 = 7 · 13 · 19
- 2465 = 5 · 17 · 29
- 2,821 = 7 · 13 · 31
- 6,601 = 7 · 23 · 41
- 8,911 = 7 · 19 · 67
最初の 33 個のカーマイケル数の昇順シーケンスは、電子整数列百科事典 (OEIS) のシーケンス n°A002997 と、最初の 8241 個のカーマイケル数のシーケンス (昇順に分類され、最初にその因数に分解されます) によって与えられます。 ）をここに示します。
J. Chernick は 1939 年に、カーマイケル数のサブセットの構築に使用できる定理を実証しました。数値 (6 k + 1)(12 k + 1)(18 k + 1) は、その 3 つの約数がすべて素数であればカーマイケル数です。 k が整数の集合を表す場合、この式またはそれに類似した他の式が無限に多くのカーマイケル数を生成するかどうかは不明です。
ポール・エルデシュは発見的に、無限に多くのカーマイケル数が存在するはずだと主張しました。この予想は1994 年に William Alford、Andrew Granville、Carl Pomerance によって実証され、より正確には、十分に大きなnに対して、1 とnの間に少なくともn 2/7カーマイケル数が存在します。
リチャード・GE・ピンチは、すべてのnに対して、それ以上のものは存在しないことを実証しました。
次の表に、この定数のおおよその値を示します。
| n | K |
| 4 | 2.19547 |
| 6 | 1.97946 |
| 8 | 1.90495 |
| 10 | 1.86870 |
| 12 | 1.86377 |
| 14 | 1.86293 |
| 16 | 1.86406 |
| 18 | 1.86522 |
| 20 | 1.86598 |
2007 年 12 月と同様に、 10 20までのカーマイケル数は 8220777 個あることが示されました。
プロパティ
カーマイケル数には少なくとも 3 つの素因数があります。
それぞれ少なくともk = 3、4、5、… の素因数を持つ最初のカーマイケル数は次のとおりです (OEIS のスイート A006931)。
| k | |
|---|---|
| 3 | 561 = 3 · 11 · 17 |
| 4 | 41041 = 7 · 11 · 13 · 41 |
| 5 | 825265 = 5 · 7 · 17 · 19 · 73 |
| 6 | 321197185 = 5 · 19 · 23 · 29 · 37 · 137 |
| 7 | 5394826801 = 7 · 13 · 17 · 23 · 31 · 67 · 73 |
| 8 | 232250619601 = 7 · 11 · 13 · 17 · 31 · 37 · 73 · 163 |
| 9 | 9746347772161 = 7 · 11 · 13 · 17 · 19 · 31 · 37 · 41 · 641 |
4 つの素因数を含む最初のカーマイケル数は次のとおりです (OEIS スイート A074379)。
| 私 | |
|---|---|
| 1 | 41041 = 7 · 11 · 13 · 41 |
| 2 | 62745 = 3 · 5 · 47 · 89 |
| 3 | 63973 = 7 · 13 · 19 · 37 |
| 4 | 75361 = 11 · 13 · 17 · 31 |
| 5 | 101101 = 7 · 11 · 13 · 101 |
| 6 | 126217 = 7 · 13 · 19 · 73 |
| 7 | 172081 = 7 · 13 · 31 · 61 |
| 8 | 188461 = 7 · 13 · 19 · 109 |
| 9 | 278545 = 5 · 17 · 29 · 113 |
| 10 | 340561 = 13 · 17 · 23 · 67 |
面白い偶然の一致は次のとおりです。3 番目のカーマイケル数と最初のチェルニック数 1729 は、ハーディ・ラマヌジャン数にほかなりません。つまり、2 つの異なる方法で 2 つの立方体の合計として書き込むことができる最小の正の整数です。 (1729 = 7 * 13* 19 = 10 3 + 9 3 = 12 3 + 1 3 )。同様に、2 番目のカーマイケル数 1105 は、それより小さい整数よりも多くの方法で 2 つの平方の和として書くことができます。シーケンスを完了するには、最初のカーマイケル数 561 を (他の自然数と同様に) より小さな正の整数よりも多くの方法で正の整数の単項累乗の合計として記述することができます。
コーセルトの定理の証明
p をカーマイケル数n を割る素数としましょう。 ( p +1) n =1+ np +C n 2 p 2 +…≡1 (mod p 2 ) となります。一方、 ( p +1) n ≡ p n +1 ≡ p + 1(mod n ) (n がカーマイケル数であるという事実から 2 番目の合同式が得られます)。 p 2がnを割った場合、 1≡( p +1) n ≡ p +1 (mod p 2 ) になりますが、これは不可能です。これは、 pの二乗がn を割らないことを示しています。
n はカーマイケル数であり、 p はnの素因数であるか、またはpの原始根を持ちます( pを伴う素数となります)。
逆に、 n がすべての異なる素数p 1 、 p 2 、… p kの積であり、数値p 1 -1、 p 2 -1、… はすべてn -1 を除算すると仮定します。次に、すべての整数aとすべてのp iについて、 a n ≡1 (mod p i -1) となるため、 a ≡ a p i ≡ a 2 p i -1 ≡ a 3 p i -2 ≡…≡ a n ( mod p i )。数値a n は、各p iのモジュロに一致するため、その積nのモジュロにも一致します。これは任意の整数aに当てはまります。したがって、 n はカーマイケル数になります。
これでコーセルトの定理の証明が完了しました。
コーセルトの定理の結果:
n をカーマイケル数とします。これはいくつかの異なる素数で割り切れるので、そのうちの少なくとも 1 つは 2 とは異なります。この奇数のn pの素約数を p と呼びましょう。 p -1 は偶数なので、その倍数n -1 も偶数です。これは、すべてのカーマイケル数が奇数であることを示しています。
p がカーマイケル数nの素因数である場合、 p -1 を法としてp ≡1≡ nが得られ、したがって 1≡( n / p ) p ≡( n / p )1= n / pとなります。言い換えれば、 p がカーマイケル数の素因数である場合、他の素因数の積は 1 を法とするp -1 に一致します。
カーマイケル数は、2 つの素数pとqの積になることはできません。その場合、2 つの数p -1 とq -1 はそれぞれ他方を除算し、等しくなるからです。
したがって、カーマイケル数は、少なくとも 3 つの異なる奇数素数の積になります。
