素数問題を解いた
数学 において 、 ベルトランの公理 （現在は 定理 ）は、各 に対して となる 素数 が存在することを述べています 。これは 1845 年に ジョセフ・ベルトランによって初めて 予想され 、 [1] チェビシェフ によって 最初に 証明され 、より簡潔ながらも高度な証明が ラマヌジャン によって与えられました。 [2]
ん ≥ 2
{\displaystyle n\geq 2}
p
{\displaystyle p}
ん < p < 2 ん
{\displaystyle n<p<2n}
以下の 初等的証明は、 ポール・エルデシュ によって1932年に発表され 、彼の初期の数学出版物の1つです。 [3]基本的な考え方は、 中心二項係数が十分に大きくなるためには、その 区間 内に 素因数 がなければならないこと を示すことです 。これは、それらの因数分解の分析によって達成されます。
（ ん 、 2 ん ）
{\displaystyle (n,2n)}
証明の主な手順は次のとおりです。まず、 中心二項係数の素数分解におけるすべての 素数べき 因数の寄与が 最大で であることを示します 。次に、 よりも大きいすべての素数が最大で 1 回出現することを示します 。
p
r
{\displaystyle p^{r}}
（
2 ん
ん
）
= （ 2 ん ） ！
/
（ ん ！
）
2
{\displaystyle \textstyle {\binom {2n}{n}}=(2n)!/(n!)^{2}}
2 ん
{\displaystyle 2n}
2 ん
{\displaystyle {\sqrt {2n}}}
次のステップは、 区間 に には素因数がないことを証明することである 。これらの境界の結果として、 の大きさへの、 最大 である素因数からの寄与は、 ある に対して として 漸近的に 増大する 。中心二項係数の漸近的増大は少なくとも であるため 、結論としては、 矛盾により 、 が十分に大きい場合、二項係数は と の 間にのみ存在する別の素因数を持つ必要がある、ということになる 。
（
2 ん
ん
）
{\displaystyle {\tbinom {2n}{n}}}
（
2 ん
3
、 ん ）
{\displaystyle ({\tfrac {2n}{3}},n)}
（
2 ん
ん
）
{\displaystyle {\tbinom {2n}{n}}}
ん
{\displaystyle n}
θ
ん
{\displaystyle \theta ^{\!\;n}}
θ < 4
{\displaystyle \theta <4}
4
ん
/
2 ん
{\displaystyle 4^{n}\!/2n}
ん
{\displaystyle n}
ん
{\displaystyle n}
2 ん
{\displaystyle 2n}
与えられた議論はすべての に対して有効です 。 の残りの値は 直接検査によって検証され、これで証明が完了します。
ん ≥ 427
{\displaystyle n\geq 427}
ん
{\displaystyle n}
証明における補題 証明では、次の 4 つの 補題 を使用して、中心二項係数に存在する素数に関する事実を確立します。
補題1 任意の整数 に対して 、
ん > 0
{\displaystyle n>0}
4
ん
2 ん
≤
（
2 ん
ん
）
。
{\displaystyle {\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}.}
証明: 二項定理 を適用すると 、
4
ん
= （ 1 + 1
）
2 ん
=
∑
け = 0
2 ん
（
2 ん
け
）
= 2 +
∑
け = 1
2 ん − 1
（
2 ん
け
）
≤ 2 ん
（
2 ん
ん
）
、
{\displaystyle 4^{n}=(1+1)^{2n}=\sum _{k=0}^{2n}{\binom {2n}{k}}=2+\sum _{k=1}^{2n-1}{\binom {2n}{k}}\leq 2n{\binom {2n}{n}},}
は右辺の和の中で最大の項であり、和には項（ 和の外側の
最初の項を含む）がある ためです。
(
2
n
n
)
{\displaystyle {\tbinom {2n}{n}}}
2
n
{\displaystyle 2n}
2
{\displaystyle 2}
補題2 固定された素数 に対して 、 を の p 進数 、つまり を割り切れる 最大の 自然数 と定義します 。
p
{\displaystyle p}
R
=
R
(
n
,
p
)
{\displaystyle R=R(n,p)}
(
2
n
n
)
{\displaystyle {\tbinom {2n}{n}}}
r
{\displaystyle r}
p
r
{\displaystyle p^{r}}
(
2
n
n
)
{\displaystyle {\tbinom {2n}{n}}}
任意の素数 に対して 、 。
p
{\displaystyle p}
p
R
≤
2
n
{\displaystyle p^{R}\leq 2n}
証明: の 指数は ルジャンドルの公式 で与えられる。
p
{\displaystyle p}
n
!
{\displaystyle n!}
∑
j
=
1
∞
⌊
n
p
j
⌋
,
{\displaystyle \sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor \!,}
それで
R
=
∑
j
=
1
∞
⌊
2
n
p
j
⌋
−
2
∑
j
=
1
∞
⌊
n
p
j
⌋
=
∑
j
=
1
∞
(
⌊
2
n
p
j
⌋
−
2
⌊
n
p
j
⌋
)
{\displaystyle R=\sum _{j=1}^{\infty }\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor =\sum _{j=1}^{\infty }\left(\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\!\left\lfloor {\frac {n}{p^{j}}}\right\rfloor \right)}
しかし、最後の和の各項はゼロ（ の場合 ）または1（ の場合 ）のいずれかでなければならず、 の項はすべて ゼロです。したがって、
n
/
p
j
mod
1
<
1
/
2
{\displaystyle n/p^{j}{\bmod {1}}<1/2}
n
/
p
j
mod
1
≥
1
/
2
{\displaystyle n/p^{j}{\bmod {1}}\geq 1/2}
j
>
log
p
(
2
n
)
{\displaystyle j>\log _{p}(2n)}
R
≤
log
p
(
2
n
)
,
{\displaystyle R\leq \log _{p}(2n),}
そして
p
R
≤
p
log
p
(
2
n
)
=
2
n
.
{\displaystyle p^{R}\leq p^{\log _{p}(2n)}=2n.}
補題3 が奇 素数 で の 場合 、
p
{\displaystyle p}
2
n
3
<
p
≤
n
{\displaystyle {\frac {2n}{3}}<p\leq n}
R
(
n
,
p
)
=
0.
{\displaystyle R(n,p)=0.}
証明: 式 の分子には の因数がちょうど 2 つあり 、これらは の 2 つの項 と に由来します。 また、 分母には の2 つの因数が それぞれ の項の1 つのコピーに由来します。これらの因数はすべて打ち消され、 には の因数は残りません 。( 補題の前提条件における に対する境界により、 は 分子の項としては大きすぎることが保証され、 が奇数であるという仮定は、 が 分子に
の 1 つの因数のみを与える ことを保証するために必要です。)
p
{\displaystyle p}
(
2
n
n
)
=
(
2
n
)
!
/
(
n
!
)
2
{\displaystyle {\tbinom {2n}{n}}=(2n)!/(n!)^{2}}
p
{\displaystyle p}
2
p
{\displaystyle 2p}
(
2
n
)
!
{\displaystyle (2n)!}
p
{\displaystyle p}
p
{\displaystyle p}
n
!
{\displaystyle n!}
p
{\displaystyle p}
(
2
n
n
)
{\displaystyle {\tbinom {2n}{n}}}
p
{\displaystyle p}
3
p
{\displaystyle 3p}
p
{\displaystyle p}
2
p
{\displaystyle 2p}
p
{\displaystyle p}
補題4 原始 関数には上限が与えられている 。
n
#
=
∏
p
≤
n
p
,
{\displaystyle n\#=\prod _{p\,\leq \,n}p,}
ここで、積は より小さいか等しいすべての 素数 に対して取られます 。
p
{\displaystyle p}
n
{\displaystyle n}
皆様 、 。
n
≥
1
{\displaystyle n\geq 1}
n
#
<
4
n
{\displaystyle n\#<4^{n}}
証明: 完全帰納法 を使います 。
なぜなら、 および があるからです 。
n
=
1
,
2
{\displaystyle n=1,2}
1
#
=
1
<
4
{\displaystyle 1\#=1<4}
2
#
=
2
<
4
2
=
16
{\displaystyle 2\#=2<4^{2}=16}
不等式がすべての に対して成り立つと仮定しましょう 。 は合成数なので、
1
≤
n
≤
2
k
−
1
{\displaystyle 1\leq n\leq 2k-1}
n
=
2
k
>
2
{\displaystyle n=2k>2}
(
2
k
)
#
=
(
2
k
−
1
)
#
<
4
2
k
−
1
<
4
2
k
.
{\displaystyle (2k)\#=(2k-1)\#<4^{2k-1}<4^{2k}.}
ここで、不等式がすべての に対して成り立つと仮定しましょう 。 は整数であり、素数はすべて 分子にのみ現れるので、
1
≤
n
≤
2
k
{\displaystyle 1\leq n\leq 2k}
(
2
k
+
1
k
)
=
(
2
k
+
1
)
!
k
!
(
k
+
1
)
!
{\displaystyle {\binom {2k+1}{k}}={\frac {(2k+1)!}{k!(k+1)!}}}
k
+
2
≤
p
≤
2
k
+
1
{\displaystyle k+2\leq p\leq 2k+1}
(
2
k
+
1
)
#
(
k
+
1
)
#
≤
(
2
k
+
1
k
)
=
1
2
[
(
2
k
+
1
k
)
+
(
2
k
+
1
k
+
1
)
]
<
1
2
(
1
+
1
)
2
k
+
1
=
4
k
.
{\displaystyle {\frac {(2k+1)\#}{(k+1)\#}}\leq {\binom {2k+1}{k}}={\frac {1}{2}}\!\left[{\binom {2k+1}{k}}+{\binom {2k+1}{k+1}}\right]<{\frac {1}{2}}(1+1)^{2k+1}=4^{k}.}
したがって、
(
2
k
+
1
)
#
=
(
k
+
1
)
#
⋅
(
2
k
+
1
)
#
(
k
+
1
)
#
≤
4
k
+
1
(
2
k
+
1
k
)
<
4
k
+
1
⋅
4
k
=
4
2
k
+
1
.
{\displaystyle (2k+1)\#=(k+1)\#\cdot {\frac {(2k+1)\#}{(k+1)\#}}\leq 4^{k+1}{\binom {2k+1}{k}}<4^{k+1}\cdot 4^{k}=4^{2k+1}.}
ベルトランの公理の証明 反例、すなわち、 n < p < 2 n となる素数 p が存在しない 整数 n ≥ 2があると仮定します 。
2 ≤ n < 427 の場合、 p は、 n < p < 2 n となるような素数 3、5、7、13、23、43、83、163、317、631 (それぞれ、前の数の 2 倍未満の最大の素数) の中から選択できます 。 したがって 、 n ≥ 427 です 。
次のような 素因数 p は存在しません:
(
2
n
n
)
{\displaystyle \textstyle {\binom {2n}{n}}}
2 n < p 、すべての因数が (2 n )を割り切れるからです 。 p = 2 n 、2 n は 素数ではない ため。 n < p < 2 n 、そのような素数は存在しないと仮定したため。 2 n / 3 < p ≤ n : 補題3より。 したがって、すべての素因数 p は p ≤ 2 n / 3
を満たします。
数が p の因数を持つのはせいぜい1 つ の場合です 。補題 2 により、任意の素数 pに対して p R ( p , n ) ≤ 2 n が成り立ち 、 1 は素数でも合成数でもありません。次に、補題 1 から始めて右辺を素因数分解し 、 最後に補題 4 を用いると、これらの境界は次のようになります。
p
>
2
n
,
{\displaystyle p>{\sqrt {2n}},}
(
2
n
n
)
{\displaystyle \textstyle {2n \choose n}}
π
(
x
)
≤
x
−
1
{\displaystyle \pi (x)\leq x-1}
4
n
2
n
≤
(
2
n
n
)
=
(
∏
p
≤
2
n
p
R
(
p
,
n
)
)
(
∏
2
n
<
p
≤
2
n
/
3
p
R
(
p
,
n
)
)
<
(
∏
p
≤
2
n
2
n
)
(
∏
p
≤
2
n
/
3
p
)
≤
(
2
n
)
2
n
−
1
4
2
n
/
3
.
{\displaystyle {\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}=\left(\,\prod _{p\,\leq \,{\sqrt {2n}}}p^{R(p,n)}\right)\!\!\left(\prod _{{\sqrt {2n}}\,<\,p\,\leq \,2n/3}\!\!\!\!\!\!\!p^{R(p,n)}\right)<\left(\,\prod _{p\,\leq \,{\sqrt {2n}}}\!\!2n\right)\!\!\left(\prod _{p\,\leq \,2n/3}\!\!p\right)\leq (2n)^{{\sqrt {2n}}-1}4^{2n/3}.}
したがって
4
n
/
3
≤
(
2
n
)
2
n
{\displaystyle 4^{n/3}\leq (2n)^{\sqrt {2n}}}
を単純化すると、
2
2
n
≤
(
2
n
)
3
.
{\displaystyle 2^{\sqrt {2n}}\leq (2n)^{3}.}
対数 を
取ると
2
n
≤
3
log
2
(
2
n
)
.
{\displaystyle {\sqrt {2n}}\leq 3\log _{2}(2n).}
右辺が nの関数として 凹である ことから 、最後の不等式は区間上で必ず証明される。これは に対しては成り立ち 、 に対しては成り立たないので 、次を得る。
n
=
426
{\displaystyle n=426}
n
=
427
{\displaystyle n=427}
n
<
427.
{\displaystyle n<427.}
しかし、これらのケースはすでに解決されており、この公理に対する反例はあり得ないと結論付けています。
証明の補遺 境界を まで縮小することが可能です 。
n
=
50
{\displaystyle n=50}
となる ので、積は 最大で となり 、
n
≥
17
,
{\displaystyle n\geq 17,}
π
(
n
)
<
n
2
−
1
{\displaystyle \pi (n)<{\frac {n}{2}}-1}
p
R
{\displaystyle p^{R}}
(
2
n
)
0.5
2
n
−
1
{\displaystyle (2n)^{0.5{\sqrt {2n}}-1}}
4
n
2
n
≤
(
2
n
n
)
≤
(
2
n
)
0.5
2
n
−
1
4
2
n
/
3
4
2
n
≤
(
2
n
)
3
2
2
n
≤
3
log
2
(
2
n
)
{\displaystyle {\begin{aligned}&{\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}\leq (2n)^{0.5{\sqrt {2n}}-1}4^{2n/3}\\&4^{\sqrt {2n}}\leq (2n)^{3}\\&2{\sqrt {2n}}\leq 3\log _{2}(2n)\end{aligned}}}
これは については真であり 、 については偽です 。
n
=
49
{\displaystyle n=49}
n
=
50
{\displaystyle n=50}
参考文献
^ Bertrand, Joseph (1845)、「Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme.」、 Journal de l'École Royale Polytechnique (フランス語)、 18 (Cahier 30) ：123～140 。 ^ ラマヌジャン、S. (1919)、「ベルトランの公準の証明」、 インド数学協会誌 、 11 : 181–182 ^ Erdős, Pál (1932)、「Beweis eines Satzes von Tschebyschef」[チェビシェフの定理の証明] (PDF) 、 Acta Scientarium Mathematicarum (セゲド) 、 5 (3–4): 194–198、 Zbl 004.10103
外部リンク チェビシェフの定理とベルトランの公理 (レオ・ゴールドマッカー): https://web.williams.edu/Mathematics/lg5/Chebyshev.pdf ベルトランの公理の証明 (UW 数学サークル): https://sites.math.washington.edu/~mathcircle/circle/2013-14/advanced/mc-13a-w10.pdf Mizar システム での証明 : http://mizar.org/version/current/html/nat_4.html#T56 Weisstein、Eric W. 「ベルトランの公理」 。MathWorld 。 
![{\displaystyle {\frac {(2k+1)\#}{(k+1)\#}}\leq {\binom {2k+1}{k}}={\frac {1}{2}}\!\left[{\binom {2k+1}{k}}+{\binom {2k+1}{k+1}}\right]<{\frac {1}{2}}(1+1)^{2k+1}=4^{k}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/655b963bd42d03c64b8397695541d9024d8075ea)
