ウォルステンホルムの定理

数学において、ウォルステンホルムの定理は、素数 に対して合同性が成り立つ ことを述べている。${\displaystyle p\geq 5}$

${\displaystyle {2p-1 \choose p-1}\equiv 1{\pmod {p^{3}}}}$

が成り立ち、括弧は二項係数を表す。例えば、p = 7 の場合、これは 1716 が 343 の倍数より 1 大きいことを意味する。この定理は1862 年にジョセフ・ウォルステンホルムによって初めて証明された。1819 年にチャールズ・バベッジはp ²を法とする同じ合同を示し、 に対して成立する。同等の定式化は合同である。 ${\displaystyle p\geq 3}$

${\displaystyle {ap \choose bp}\equiv {a \choose b}{\pmod {p^{3}}}}$

はWilhelm Ljunggren ^[1]（特殊なケースではJWL Glaisher ^[要出典]）によるものであり、 Lucas の定理にヒントを得たものです。 ${\displaystyle p\geq 5}$${\displaystyle b=1}$

ウォルステンホルムの定理を満たす合成数は知られておらず、存在しないと推測されています (下記参照)。p ^{4を法として合同性を満たす素数は}ウォルステンホルム素数と呼ばれます(下記参照)。

ウォルステンホルム自身が確立したように、彼の定理は（一般化された）調和数に対する一対の合同式として表現することもできる。

${\displaystyle 1+{1 \over 2}+{1 \over 3}+\dots +{1 \over p-1}\equiv 0{\pmod {p^{2}}}{\mbox{、そして}}}$

${\displaystyle 1+{1 \over 2^{2}}+{1 \over 3^{2}}+\dots +{1 \over (p-1)^{2}}\equiv 0{\pmod {p}}.}$

以来

${\displaystyle {2p-1 \choose p-1}=\prod _{1\leq k\leq p-1}{\frac {2p-k}{k}}\equiv 1-2p\sum _{1\leq k\leq p-1}{\frac {1}{k}}{\pmod {p^{2}}}}$

(分数との合同性は、分母が係数と互いに素である場合に意味を持ちます。) たとえば、p =7 の場合、最初の式は分子の 49/20 が 49 の倍数であることを示しますが、2 番目の式は分子の 5369/3600 が 7 の倍数であることを示します。

素数p は、次の条件が満たされる 場合にのみ、ウォルステンホルム素数と呼ばれます。

${\displaystyle {{2p-1} \choose {p-1}}\equiv 1{\pmod {p^{4}}}.}}$

p がウォルステンホルム素数であれば、 p ⁴を法としてグレイシャーの定理が成り立つ。これまでに知られているウォルステンホルム素数は 16843 と 2124679 ( OEISのシーケンスA088164 ) のみであり、その他のウォルステンホルム素数は 10 ¹¹より大きくなければならない。^[2]この結果は、p ⁴を法とする剰余はp ³の疑似乱数の倍数であるという経験的議論と一致する。この経験的議論によれば、 KとNの間にあるウォルステンホルム素数の数はおよそln ln N − ln ln K である。ウォルステンホルム条件は 10 ¹¹まで検証されており、経験的議論によれば 10 ¹¹と 10 ²⁴の間にはおよそ 1 つのウォルステンホルム素数が存在するはずである。同様のヒューリスティックにより、 p ⁵を法として合同が成立する「二重ウォルステンホルム」素数は存在しないことが予測されます。

ウォルステンホルムの定理を証明する方法は複数あります。ここでは、組合せ論と代数の両方を使用してグレイシャーのバージョンを直接証明する証明を示します。

とりあえずp を任意の素数、aとb を任意の非負整数とする。すると、ap個の元を持つ集合A は長さpの環に分割でき、環は別々に回転できる。したがって、位数pの巡回群のa重直和は集合Aに作用し、拡張するとサイズbpの部分集合の集合にも作用する。この群作用のすべての軌道にはp ^k個の元があり、kは不完全な環の数、つまり軌道上で部分集合Bと部分的にしか交差しない環がk個ある場合である。サイズ 1 の軌道は存在するが、サイズpの軌道は存在しない。^[3]したがって、まずバベッジの定理が得られる。 ${\displaystyle \textstyle {a \choose b}}$

${\displaystyle {ap \choose bp}\equiv {a \choose b}{\pmod {p^{2}}}.}$

サイズp ²の軌道を調べると、次の式も得られます。

${\displaystyle {ap \choose bp}\equiv {a \choose b}+{a \choose 2}\left({2p \choose p}-2\right){a-2 \choose b-1}{\pmod {p^{3}}}.}$

この式から分かることは、他の結果の中でも、a=2かつb=1の場合がウォルステンホルムの定理の 2 番目の形式の一般的なケースを意味するということです。

組合せ論から代数に移ると、この合同式の両辺は、bの固定値ごとにaの多項式となる。したがって、 bが固定された正の整数であれば、 aが正または負の任意の整数のときに合同式が成立する。特に、a=-1かつb=1の場合、合同式は次のようになる。

${\displaystyle {-p \choose p}\equiv {-1 \choose 1}+{-1 \choose 2}\left({2p \choose p}-2\right){\pmod {p^{3}}}.}$

この合同は、関係式を使用する ための方程式となる。${\displaystyle \textstyle {2p \choose p}}$

${\displaystyle {-p \choose p}={\frac {(-1)^{p}}{2}}{2p \choose p}.}$

pが奇数のとき、関係は

${\displaystyle 3{2p \choose p}\equiv 6{\pmod {p^{3}}}.}$

p ≠3の場合、両辺を 3 で割って議論を完了することができます。

同様の導出をp4^を法として行うと、

${\displaystyle {ap \choose bp}\equiv {a \choose b}{\pmod {p^{4}}}}$

すべての正のaおよびbに対して、 a=2かつb=1 のときに成り立つ場合、つまり、pがウォルステンホルム素数のときに限ります。

もし

k =3のとき、nは素数です。この予想は、k = 1 と 2 だけでなく 3 も考えることで理解できます。k = 1 のとき、バベッジの定理によれば、p が奇数の素数であればn = p 2 が成り立ち、ウォルステンホルムの定理によれば、p > 3であればn = p ³が成り立ち、p がウォルステンホルム素数であればn = p ^{4が成り立ちます。k = 2}のとき、 p がウォルステンホルム素数であればn = p ²が成り立ちます。これら3つの数、4 = 2 ²、8 = 2 ³、27 = 3 ^3は、( 1 ) k = 1 では成り立ちませんが、他のすべての素数の平方と素数の立方では、( 1 ) k = 1 で成り立ちます。nの他の5つの合成値（素数の平方でも素数の立方でもない）のみが、 ( 1 ) k = 1 で成り立つことが知られており、これらはウォルステンホルム擬素数と呼ばれ、

27173、2001341、16024189487、80478114820849201、20378551049298456998947681、...（OEISの配列A082180）

最初の 3 つは素数累乗ではない ( OEISのシーケンスA228562 )、最後の 2 つは 16843 ⁴と 2124679 ⁴で、 16843 と 2124679 はウォルステンホルム素数である ( OEISのシーケンスA088164 )。さらに、 16843 ²と 2124679 ²の例外を除いて、( 1 ) でk = 2 のとき、ましてやk = 3 のとき、成立する合成数は知られていない。したがって、ウォルステンホルムの合同は合成数に対しては過度に制約され不自然であると思われるため、この予想は妥当であると考えられる。さらに、合同が素数または素数累乗以外の任意のnと任意の特定のkに対して成立するとしても、次のことを意味しない。

${\displaystyle {an \choose bn}\equiv {a \choose b}{\pmod {n^{k}}}.}$

までのウォルステンホルム擬素数の数は なので、それらの数の逆数の和は収束します。 定数は、までのウォルステンホルム擬素数が 3 つだけ存在することから導かれます。 までのウォルステンホルム擬素数の数は、その逆数の和が発散する場合、少なくとも 7 である必要がありますが、この範囲には 3 つしかないため、この条件は満たされません。したがって、これらの擬素数の計数関数は、ある効率的に計算可能な定数 に対して最大で です。つまり、とすることができます。ビッグオー記法の定数も、 で効果的に計算可能です。 ${\displaystyle x}$${\displaystyle O(x^{1/2}\log(\log(x))^{499712})}$${\displaystyle 499712}$${\displaystyle 10^{12}}$${\displaystyle 10^{12}}$${\displaystyle O(x^{1/2}\log(\log(x))^{C})}$${\displaystyle C}$${\displaystyle C}$${\displaystyle 499712}$${\displaystyle O(x^{1/2}\log(\log(x))^{499712})}$

ロイデスドルフは、6と互いに素な正の整数nに対して、次の合同が成り立つことを証明した。^[4]

${\displaystyle \sum _{i=1 \atop (i,n)=1}^{n-1}{\frac {1}{i}}\equiv 0{\pmod {n^{2}}}.}$

1900年にグレイシャー^{[5] [6]}はさらに次のことを示した。素数p>3の場合、

${\displaystyle {\binom {2p-1}{p-1}}\equiv 1-{\frac {2p^{3}}{3}}B_{p-3}{\pmod {p^{4}}}.}$

ここで、B_n はベルヌーイ数です。

• フェルマーの小定理
• ウィルソンの定理
• ヴィーフェリヒ素数
• ウィルソンプライム
• 壁-太陽-太陽プライム
• 素数の特別なクラスのリスト
• 合同表

• バベッジ、C.（1819）「素数に関する定理の証明」、エディンバラ哲学ジャーナル、1：46-49。
• グレイシャー、JWL（1900）、「最初のn個の数の積の和とその他の積の和に関する合同性」、純粋および応用数学の季刊誌、31：1-35。
• ^{グレイシャー、JWL（1900）、「二項定理係数のp 3}に関する剰余」、純粋および応用数学の季刊誌、31：110-124。
• グレイシャー、JWL（1900）「最初のp−1個の数とその累乗の積の和の剰余について、p ²またはp ^{3 を}法として」、純粋および応用数学の季刊誌、31：321–353。
• Granville, Andrew (1997)、「素数べきを法とする二項係数」(PDF)、Canadian Mathematical Society Conference Proceedings、20 : 253–275、MR 1483922、2017-02-02に オリジナル(PDF)からアーカイブ。
• McIntosh, RJ (1995)、「ウォルステンホルムの定理の逆について」(PDF)、Acta Arithmetica、71 (4): 381–389、doi : 10.4064/aa-71-4-381-389。
• R. メストロヴィッチ、「ウォルステンホルムの定理：過去 150 年間におけるその一般化と拡張 (1862 〜 2012 年)」。
• ウォルステンホルム、ジョセフ（1862）「素数の特定の性質について」、純粋および応用数学季刊誌、5：35-39。

• プライム用語集: ウォルステンホルムプライム
• ウォルステンホルム素数の検索ステータス