カーマイケル数

数論において、カーマイケル数は、モジュラー算術において合同関係を 満たす合成数 である。${\displaystyle n}$

${\displaystyle b^{n}\equiv b{\pmod {n}}}$

すべての整数⁠ ⁠${\displaystyle b}$に対して。^{[1]この関係は[2] の}形式で も表される。

${\displaystyle b^{n-1}\equiv 1{\pmod {n}}}$

⁠ ⁠と互いに素であるすべての整数に対して。それらは無限個である。^[3]${\displaystyle b}$${\displaystyle n}$

これらはフェルマーの小定理の厳密な逆が成り立たない比較的稀な例である。この事実は、その定理を素数性の絶対的なテストとして使用することを妨げている。^[4]

カーマイケル数はクネーデル数のサブセットK ₁を形成します。

カーマイケル数は、1950年にニコラス・ビーガーによってアメリカの数学者ロバート・カーマイケルにちなんで命名されました。オイステイン・オーレは1948年にこれを「フェルマーの性質」を持つ数、略して「 F数」と呼んでいました。 ^[5]

フェルマーの小定理は、 が素数である場合、任意の整数⁠ ⁠に対して、その数は⁠ ⁠の整数倍であると述べています。カーマイケル数は、同じ特性を持つ合成数です。カーマイケル数は、フェルマー擬素数または絶対フェルマー擬素数とも呼ばれます。カーマイケル数は、実際には素数でなくても、その数と互いに素であるすべての基数に対してフェルマー素数判定に合格します。このため、フェルマーの小定理に基づくテストは、ベイリー–PSW素数判定テストやミラー–ラビン素数判定テストなどの強力な確率素数テストよりも有効性が低くなります。 ${\displaystyle p}$ ${\displaystyle b}$${\displaystyle b^{p}-b}$${\displaystyle p}$${\displaystyle b}$

しかし、カーマイケル数はオイラー・ヤコビ擬素数でも、それと互いに素なすべての基数に対する強擬素数でもない^[6] ため、理論的には、オイラーまたは強確率素数テストのいずれかによって、カーマイケル数が実際には合成数であることを証明できる可能性がある。

アルノー^[7]は、 307未満の すべての素数基数に対する強い擬素数である 397桁のカーマイケル数を与えている。${\displaystyle N}$

${\displaystyle N=p\cdot (313(p-1)+1)\cdot (353(p-1)+1)}$

どこ

${\displaystyle p=}$ 2 9674495668 6855105501 5417464290 5332730771 9917998530 4335099507 5531276838 7531717701 9959423859 6428121188 0336647542 1834556249 3168782883

は 131 桁の素数です。は⁠ ⁠の最小の素因数なので、このカーマイケル数は⁠ ⁠未満のすべての基数に対して (必ずしも強いとは限りませんが) 擬素数でもあります。 ${\displaystyle p}$${\displaystyle N}$${\displaystyle p}$

数が大きくなるにつれて、カーマイケル数はますます稀になります。たとえば、1から10 ²¹の間には20,138,200個のカーマイケル数があります（約50兆（5·10 ¹³）個の数に1つ）。^[8]

カーマイケル数の代替かつ同等の定義は、コルセルトの基準によって与えられます。

定理( A. Korselt 1899): 正の合成整数がカーマイケル数である場合、かつその場合のみ、 は平方数ではなく、 ⁠ ⁠のすべての素因数に対して⁠ ⁠が真です。${\displaystyle n}$${\displaystyle n}$ ${\displaystyle p}$${\displaystyle n}$${\displaystyle p-1\mid n-1}$

この定理から、すべてのカーマイケル数は奇数であることがわかります。なぜなら、平方根のない偶数の合成数（したがって、2の素因数を1つだけ持つ）は、少なくとも1つの奇数の素因数を持ち、したがって奇数を偶数で割ることになり、矛盾が生じるからです。（カーマイケル数が奇数であることは、任意の偶数の合成数に対してがフェルマーの証人であるという事実からもわかります。）この基準から、カーマイケル数は巡回数であることもわかります。^{[9] [10]}さらに、ちょうど2つの素因数を持つカーマイケル数は存在しないことになります。 ${\displaystyle p-1\mid n-1}$${\displaystyle -1}$

カーマイケル数の最初の7つ、561から8911まではすべて、1885年にチェコの数学者ヴァーツラフ・シメルカによって発見された^[11]（したがって、カーマイケルだけでなくコルセルトよりも先行していたが、シメルカはコルセルトの基準のようなものは発見しなかった）。^[12]しかし、チェコの科学雑誌「Časopis pro pěstování matematiky a fysiky」に掲載された彼の研究は注目されなかった。

コルセルトはカーマイケル数の基本的な性質を観察した最初の人物であったが、例を挙げなかった。

561 がカーマイケル数であることは、コルセルトの基準でわかります。確かに、は平方数ではなく、⁠ ⁠、⁠ ⁠です。次の 6 つのカーマイケル数は ( OEISのシーケンスA002997 ) です。 ${\displaystyle 561=3\cdot 11\cdot 17}$${\displaystyle 2\mid 560}$${\displaystyle 10\mid 560}$${\displaystyle 16\mid 560}$

${\displaystyle 1105=5\cdot 13\cdot 17\qquad (4\mid 1104;\quad 12\mid 1104;\quad 16\mid 1104)}$

${\displaystyle 1729=7\cdot 13\cdot 19\qquad (6\mid 1728;\quad 12\mid 1728;\quad 18\mid 1728)}$

${\displaystyle 2465=5\cdot 17\cdot 29\qquad (4\mid 2464;\quad 16\mid 2464;\quad 28\mid 2464)}$

${\displaystyle 2821=7\cdot 13\cdot 31\qquad (6\mid 2820;\quad 12\mid 2820;\quad 30\mid 2820)}$

${\displaystyle 6601=7\cdot 23\cdot 41\qquad (6\mid 6600;\quad 22\mid 6600;\quad 40\mid 6600)}$

${\displaystyle 8911=7\cdot 19\cdot 67\qquad (6\mid 8910;\quad 18\mid 8910;\quad 66\mid 8910).}$

1910年にカーマイケル自身^[13]もそのような最小の数561を発表し、後にこれらの数は彼にちなんで命名されました。

ジャック・チャーニック^{[14]は1939年にカーマイケル数の}サブセットを構成する定理を証明した。その数は3つの因数がすべて素数である場合にカーマイケル数である。この式が無限個のカーマイケル数を生成するかどうかは未解決の問題である（ただし、それはディクソンの予想によって示唆されている）。 ${\displaystyle (6k+1)(12k+1)(18k+1)}$

ポール・エルデシュは、カーマイケル数は無限に存在するはずだと経験的に主張した。1994年にWR（レッド）アルフォード、アンドリュー・グランビル、カール・ポメランスはオルソン定数 の上限を用いて、カーマイケル数が本当に無限に存在することを示しました。具体的には、十分に大きい に対して、 1から⁠ ⁠ の間に少なくともカーマイケル数が存在することを示した。^[3]${\displaystyle n}$${\displaystyle n^{2/7}}$${\displaystyle n}$

トーマス・ライトは、とが互いに素であれば、等差数列⁠ ⁠（ただし⁠ ⁠ ）にはカーマイケル数が無限に存在することを証明した。^[15]${\displaystyle a}$${\displaystyle m}$ ${\displaystyle a+k\cdot m}$${\displaystyle k=1,2,\ldots }$

1992年にレーとニーバーは、1,101,518個の因数と1600万桁を超える桁を含む、非常に大きなカーマイケル数をいくつか発見しました。これは、10,333,229,505個の素因数と295,486,761,787桁にまで改善されており、^{[16]既知の最大のカーマイケル数は}、既知の最大の素数よりもはるかに大きいです。

カーマイケル数には少なくとも 3 つの正の素因数があります。素因数を持つ最初のカーマイケル数は次のとおりです ( OEISのシーケンスA006931 )。 ${\displaystyle k=3,4,5,\ldots }$

4 つの素因数を持つ最初のカーマイケル数は次のとおりです ( OEISのシーケンスA074379 )。

2 番目のカーマイケル数 (1105) は、2 つの平方数の和として、より小さい数よりも多くの方法で表現できます。3 番目のカーマイケル数 (1729) はハーディ・ラマヌジャン数です。これは、2 つの異なる方法で2 つの立方数 (正の数) の和として表現できる最小の数です。

⁠ ⁠以下のカーマイケル数の個数を とします。10の累乗によるカーマイケル数の分布（OEISのシーケンスA055553）は次のとおりです。^[8]${\displaystyle C(X)}$${\displaystyle X}$

1953年、クネーデルは上限を証明した。

${\displaystyle C(X)<X\exp \left({-k_{1}\left(\log X\log \log X\right)^{\frac {1}{2}}}\right)}$

ある定数⁠ ⁠${\displaystyle k_{1}}$に対して。

1956年にエルデシュは、

${\displaystyle C(X)<X\exp \left({\frac {-k_{2}\log X\log \log \log X}{\log \log X}}\right)}$

ある定数⁠ ⁠${\displaystyle k_{2}}$に対して。^[17]彼はさらに、この上限は⁠ ⁠の真の成長率に近いはずであると示唆する経験的な議論を示した。 ${\displaystyle C(X)}$

一方、アルフォード、グランビル、ポメランスは1994年に^{[3]、十分に大きい}Xに対して、

${\displaystyle C(X)>X^{\frac {2}{7}}.}$

2005年に、この境界はハーマン^[18]によってさらに改良され、

${\displaystyle C(X)>X^{0.332}}$

彼はその後指数を⁠ ⁠${\displaystyle 0.7039\cdot 0.4736=0.33336704>1/3}$に改良した。^[19]

カーマイケル数の漸近分布に関しては、いくつかの予想がなされている。1956年にエルデシュ^[17]は、 Xが十分に大きい場合、カーマイケル数が存在すると予想した。1981年にポメランス^[20]は、エルデシュのヒューリスティックな議論を洗練させ、少なくとも ${\displaystyle X^{1-o(1)}}$

${\displaystyle X\cdot L(X)^{-1+o(1)}}$

カーマイケル数は⁠ ⁠${\displaystyle X}$までです(ただし⁠ ⁠ )${\displaystyle L(x)=\exp {\left({\frac {\log x\log \log \log x}{\log \log x}}\right)}}$。

^{しかし、現在の計算範囲内（ピンチ[8]が実行したカーマイケル数の1021}までのカウントなど）では、これらの推測はまだデータによって裏付けられていません。

2021年、ダニエル・ラーセンは、 1994年にアルフォード、グランヴィル、ポメランスによって初めて予想されたカーマイケル数に対するベルトランの公理の類似物を証明した。^{[4] [21]}張一唐とジェームズ・メイナードによって開発された手法を使用して、素数間の小さなギャップに関する結果を確立し、彼の研究は、任意のおよびに関して十分に大きいに対して、常に少なくとも ${\displaystyle \delta >0}$${\displaystyle x}$${\displaystyle \delta }$

${\displaystyle \exp {\left({\frac {\log {x}}{(\log \log {x})^{2+\delta }}}\right)}}$

カーマイケル数は～ ${\displaystyle x}$

${\displaystyle x+{\frac {x}{(\log {x})^{\frac {1}{2+\delta }}}}.}$

カーマイケル数の概念は、任意の数体 ⁠ ⁠におけるカーマイケルイデアルに一般化されます。 ${\displaystyle K}$⁠ ⁠内の任意の非ゼロ素イデアルに対して、 ⁠ ⁠内のすべての ⁠ ⁠ に対してが成り立ちます。ここで はイデアル⁠ ⁠のノルムです。(これは、 ⁠ ⁠が素数のとき、すべての整数⁠ ⁠ ⁠に対して となるというフェルマーの小定理を一般化したものです。) 非ゼロのイデアルが素イデアルでなく、すべての⁠ ⁠に対して がイデアル⁠ ⁠のノルムである場合、そのイデアルをカーマイケルと呼びます。 ⁠ ⁠が⁠ ⁠のとき、イデアルは主イデアルであり、⁠ ⁠ をその正の生成元とすると、 ⁠ ⁠ が通常の意味でのカーマイケル数であるときとまったく同じように、イデアルはカーマイケルです。 ${\displaystyle {\mathfrak {p}}}$${\displaystyle {\mathcal {O}}_{K}}$${\displaystyle \alpha ^{{\rm {N}}({\mathfrak {p}})}\equiv \alpha {\bmod {\mathfrak {p}}}}$${\displaystyle \alpha }$${\displaystyle {\mathcal {O}}_{K}}$${\displaystyle {\rm {N}}({\mathfrak {p}})}$ ${\displaystyle {\mathfrak {p}}}$${\displaystyle m^{p}\equiv m{\bmod {p}}}$${\displaystyle m}$${\displaystyle p}$${\displaystyle {\mathfrak {a}}}$${\displaystyle {\mathcal {O}}_{K}}$${\displaystyle \alpha ^{{\rm {N}}({\mathfrak {a}})}\equiv \alpha {\bmod {\mathfrak {a}}}}$${\displaystyle \alpha \in {\mathcal {O}}_{K}}$${\displaystyle {\rm {N}}({\mathfrak {a}})}$${\displaystyle {\mathfrak {a}}}$${\displaystyle K}$${\displaystyle \mathbf {Q} }$${\displaystyle {\mathfrak {a}}}$${\displaystyle a}$${\displaystyle {\mathfrak {a}}=(a)}$${\displaystyle a}$

⁠ ⁠が${\displaystyle K}$有理数より大きい場合、 ⁠ ⁠${\displaystyle {\mathcal {O}}_{K}}$のカーマイケル イデアルを簡単に記述できます。 ⁠ ⁠で完全に分割される任意の素数⁠ ⁠${\displaystyle p}$に対して、主イデアルはカーマイケル イデアルです。任意の数体で完全に分割される素数は無限にあるため、⁠ ⁠にはカーマイケル イデアルが無限に存在します。たとえば、⁠ ⁠ が1 mod 4 である任意の素数である場合、ガウス整数のイデアル⁠ ⁠はカーマイケル イデアルです。 ${\displaystyle K}$${\displaystyle p{\mathcal {O}}_{K}}$${\displaystyle {\mathcal {O}}_{K}}$${\displaystyle p}$${\displaystyle (p)}$ ${\displaystyle \mathbb {Z} [i]}$

素数とカーマイケル数は両方とも次の等式を満たします。

${\displaystyle \gcd \left(\sum _{x=1}^{n-1}x^{n-1},n\right)=1.}$

正の合成整数がルーカス・カーマイケル数である場合、かつ が平方数でない場合に限り、⁠ ⁠のすべての素因数に対して⁠ ⁠が真です。最初のルーカス・カーマイケル数は次のとおりです。 ${\displaystyle n}$${\displaystyle n}$ ${\displaystyle p}$${\displaystyle n}$${\displaystyle p+1\mid n+1}$

399、935、2015、2915、4991、5719、7055、8855、12719、18095、20705、20999、22847、29315、31535、46079、51359、60059、63503、67199、73535、76751、80189、81719、88559、90287、...（OEISのシーケンスA006972）

準カーマイケル数は、 のすべての素因数 に対して、 が を正に割り切る（ は 0 以外の任意の整数）という性質を持つ平方のない合成数です。の場合、これらはカーマイケル数であり、の場合${\displaystyle n}$、これらはルーカス・カーマイケル数です。最初の準カーマイケル数は次のとおり です。${\displaystyle p}$${\displaystyle n}$${\displaystyle p+b}$${\displaystyle n+b}$${\displaystyle b}$${\displaystyle b=-1}$${\displaystyle b=1}$

35、77、143、165、187、209、221、231、247、273、299、323、357、391、399、437、493、527、561、589、598、713、715、899、935、943、989、1015、1073、1105、1147、1189、1247、1271、1295、1333、1517、1537、1547、1591、1595、1705、1729 、 ...（OEIS )

与えられた正の整数nに対するn -クネーデル数は、mと互いに素な各⁠ ⁠ が⁠ ⁠を満たすという性質を持つ合成数mです。⁠ ⁠の場合はカーマイケル数です。 ${\displaystyle i<m}$ ${\displaystyle i^{m-n}\equiv 1{\pmod {m}}}$${\displaystyle n=1}$

カーマイケル数は抽象代数の概念を使って一般化することができます。

上記の定義は、合成整数nがカーマイケル関数であるのは、nを法とする整数の環Z n_からのn乗関数p _{n が}恒等関数である場合に限ると述べています。恒等関数はZ _n上の唯一のZ _n -代数自己準同型なので、 p _nがZ _nの代数自己準同型であることを要求していると定義を言い換えることができます。上記のように、nが素数である場合は常にp _{n は}同じ特性を満たします。

n乗関数p _{n は}任意のZ _n代数A上でも定義されます。定理によれば、そのような関数p _{n が}すべて代数自己準同型である場合に限り、nは素数と なります。

これら 2 つの条件の間に、任意の正の整数mに対するm 次カーマイケル数の定義が存在します。これは、 p _{n が}、 m個の要素によってZ _nモジュールとして生成できるすべてのZ _n代数上の自己準同型であるような任意の合成数nです。1 次カーマイケル数は、通常のカーマイケル数と同じです。

ハウによれば、17・31・41・43・89・97・167・331は2次のカーマイケル数である。この積は443,372,888,629,441に等しい。^[22]

ハウが示したように、コルセルトの基準は高次のカーマイケル数に一般化できます。

同じ論文で提示された経験的議論によれば、任意のmに対して、m次カーマイケル数は無限に存在することが示唆されているようです。しかし、 3 次以上のカーマイケル数は 1 つも知られていません。

• カーマイケル、RD ( 1910)。「新しい数論関数に関するノート」。アメリカ数学会報。16 (5): 232–238。doi : 10.1090/ s0002-9904-1910-01892-9。
• カーマイケル、 RD (1912)。「フェルマー合同を満たす合成数Pについて」アメリカ数学月刊誌。19 (2): 22–27。doi :10.2307/2972687。JSTOR  2972​​687。${\displaystyle a^{P-1}\equiv 1{\bmod {P}}}$
• Chernick, J. (1939). 「フェルマーの簡単な定理について」(PDF) . Bull. Amer. Math. Soc . 45 (4): 269–274. doi : 10.1090/S0002-9904-1939-06953-X .
• アーカンソー州コーセルト（1899年）。 「問題のシノワ」。L'Intermédiaire des Mathématiciens。6 : 142–143。
• Löh, G.; Niebuhr, W. (1996). 「大きなカーマイケル数を構築するための新しいアルゴリズム」(PDF) . Math. Comp . 65 (214): 823–836. Bibcode :1996MaCom..65..823L. doi : 10.1090/S0025-5718-96-00692-8 . 2003-04-25 にオリジナルからアーカイブ(PDF)されました。
• リベンボイム、P. (1989)。素数記録の書。シュプリンガー。ISBN 978-0-387-97042-4。
• シメルカ、V. (1885)。 「Zbytky z arithmetické posloupnosti (等差数列の余りについて)」。Časopis Pro Pěstování Matematiky a Fysiky。14 (5): 221–225。土井: 10.21136/CPMF.1885.122245。

• 「カーマイケル数」、数学百科事典、EMS Press、2001 [1994]
• 数学百科事典
• カーマイケル数表
• 多くの素因数を持つカーマイケル数の表
• 10 18 未満のカーマイケル数の表 {\displaystyle 10^{18}}
• 「1729 年の退屈さ」。MathPages.com。
• Weisstein、Eric W.「カーマイケル数」。MathWorld。
• 最終解答 モジュラー算術