For every n ≥ 1, there is some prime number p with n < p ≤ 2n.
■Proof. We will estimate the size of the binomial coefficient 
carefully enough to see that if it didn't have any prime factors in the range n < p ≤ 2n, then it would be "too small." Our argument is in five steps.
(1) We first prove Bertrand's postulate for n ≤ 511. For this one does not need to check 511 cases: it suffices (this is "Landau's trick") to check that
is a sequence of prime numbers, where each is smaller than twice the previous one. Hence every interval {y：n < y ≤ 2n}, with n ≤ 511, contains one of these 11 primes.
(2) Next we prove that
where our notation ― here and in the following ― is meant to imply that the product is taken over all prime numbers p ≤ x. The proof that we present for this fact uses induction on the number of these primes. First we note that if q is the largest prime with q ≤ x, then
Thus it suffices to check (1) for the case where x = q is a prime number. For q = 2 we get "2 ≤ 4," so we proceed to consider odd primes q = 2m + 1. (Here we may assume, by induction, that (1) is valid for all integers x in the set {2,3,...,2m}.) For q = 2m + 1 we split the product and compute
All the pieces of this "one-line computation" are easy to see. In fact,
holds by induction. The inequality
follows from the observation that 
is an integerm, where tha primes that we consider all are factors of the numerator (2m + 1)!, but not of the denominator m!(m + 1)!. Finally
holds since
are two (equal!) summands that appear in
(3) From †Legendre's theorem we get that 
contains the prime factor p exactly
times. Here each summand is at most 1, since it satisfies
and it is an integer. Furthermore the summands vanish whenever pk > 2n. Thus 
contains p exactly
times. Hence the largest power of p that divides is not larger than 2n. In particular, primes 
appear at most once in .
Furthemore ― and this, according to Erdős, is the key fact for his proof ― primes p that satisfy 
do not divide at all! Indeed, 3p > 2n implies (for n ≥ 3, and hence p ≥ 3) that p and 2p are the only multiples of p that appear as factors in the numerator of 
, while we get two p-factors in the denominator.
(4) Now we are ready to estimate , benefitting from a suggestion by Raimund Seidel, which nicely improves Erdős' original argument. For n ≥ 3, using an estimate from ††page 14 for the lower bound, we get
Now, there are no more than 
primes in the first factor; hence using (1) for the second factor and letting P(n) denote the number of primes between n and 2n we get
that is,
(5) Taking the logarithm to base 2, the last inequality is turned into
It remains to verify that the right-hand side of (3) is positive for n large enough. We show that this is the case for n = 29 = 512 (actually, it holds from n = 468 onward). By writing 
and cancelling the 
-factor it suffices to show
For n = 29, (4) becomes 31 > 30, and comparing the derivatives
we see that 
grows faster than 
and thus certainly for x ≥ 210 = 1024. □
出典:Martin Aigner and Günter M.Ziegler. Proofs from THE BOOK P9. Chapter 2
―――――――――――――――――――――――――――――――――――――――――――
訳と補足:
まず、原典の余白に記載されている†ルジャンドルの定理の証明の訳を記す。
補題1.ルジャンドルの定理
n!に含まれる素因数pは厳密に
個である。
証明:厳密にpで割り切れるn! = 1・2・3…nの因数
とは、因数pについて個である。次にp2によっても割り切れるn!の因数
とは、n!の因数pが個ある。これを繰り返す。□
次に、原書††14ページの下界の概算を示す。
補題2.
証明:集合nの部分集合kの数は、二項係数
の定義により、二項係数の数列
については、和と対称性が
であることがわかる(パスカルの三角形)。
全てのnについて、この数列から、二項係数は対称性と単峰性(中心に向かって増大し、数列の中心の二項係数が最大になる)
があることが、関数方程式
から簡単にわかる。
上記の二項係数の階乗についての漸近公式から、二項係数の大きさの非常に正確な概算を得ることができる。しかしながら、ここでは弱く簡単な概算のみが必要であり、その場合、全てのkにより、
であると同時に、n ≥ 2のとき
となり、n = 2のときに等号が成立つ。特に、n ≥ 1のとき
□
これより、本題の証明を行う。
ベルトランの仮説:全てのn ≥ 1において、n < p ≤ 2nとなる素数pが存在する。
証明:n < p ≤ 2nの範囲に素因数を持たないならば、それは｢非常に小さい｣ことに十分注意して、二項係数の大きさを概算しよう。論点は5つある。
(1)まず、n ≤ 511でベルトランの仮説を確かめる。この場合、511を確かめる必要はない。例として、素数の数列
を調べれば良く("ランダウのトリック"である)、それぞれの数は前の数の2倍よりも小さい。これよりn ≤ 511で、全ての区間{y：n < y ≤ 2n}は、これらの11個の素数のいずれかが含まれる。
(2)次に
を確かめる。この記号は(これ以降)、全ての素数p ≤ xに渡る積を意味する。この証明は、これらの素数で帰納法を用いることで示す。まず、qが最大の素数q ≤ xであるならば、
に気を付ける。従って、例えばx = qは素数であるため、式(1)を調べれば良い。q = 2で｢2 ≤ 4｣を得る。そして、奇素数q = 2m + 1で考える。(ここで、帰納法によって、集合{2,3,...,2m}に含まれる全ての整数xから、式(1)は確かであることを仮定する。)q = 2m + 1の場合、この積を分けて計算すると
となる。この｢一行の計算｣の全ての部分は、簡単にわかる。実際に、帰納法により
となる。この不等式
は、分子(2m + 1)!の因数を全て考えると素数であるが、分母m!(m + 1)!は素数ではないことから、は整数であるという結果を得る。最後に
である。これは
が
で表わされる2つの(等しい)被加数である。
(3)†ルジャンドルの定理からに含まれる素因数pは厳密に
個であることを得る。ここで、それぞれの被加数はせいぜい1である。これは、
を満たし、整数である。さらに、被加数を消すときは必ずpk > 2nである。従って、に含まれるpは厳密に
個である。これより、最大のpのべきで割り切れるは2nよりも小さい。特に、素数はに一度だけ現れる。
さらに、を満たす素数pは全て、を割れない(エルデシュによると、この証明の要所である)。実際に、3p > 2nは、の分子の因数から生じると同時に、分母の2つの因数pの倍数であるpと2pを含む(n ≥ 3の場合、これよりp ≥ 3)。
(4)ここで、ライムント・ザイデルの提案から、恩恵を受けてエルデシュが上手く改良したオリジナルの議論より、の概算の準備ができた。n ≥ 3のとき、††14ページの下界の概算を用いると、
を得る。ここで、最初の因数はの素数よりも大きくない。これより、式(1)を2つ目の因数に用いて、nと2nの間の素数の数をP(n)と書くとすると
を得る。これは
である。
(5)底を2で対数をとると、最後の不等式は
となる。式(3)の右辺は正のnが十分大きい場合に確かめるためにある。n = 29 = 512の場合を見る(実際にはn = 468以降)。と書くと、因数は打ち消されて
を満たす。n = 29の場合、式(4)は31 > 30となり、導関数を比較すると、はより早く増加し、確かにx ≥ 210 = 1024についても成り立つ。□
―――――――――――――――――――――――――――――――――――――――――――
ベルトランの仮説改め、チェビシェフの定理は素数の分布に関する定理である。
証明としては、エルデシュが高校生の時に示したという初等的な証明と似たものを用いたが、様々な分野の計算を用いているため、1つ1つは簡単でも全てを確かめるのは、なかなか体力を使った。
この証明の特徴としては、証明が難しい小さい範囲では実際に値を1つずつ代入して求めて、残りの大きな範囲でnと2nの間に素数が存在しないとすると、式(3)の不等式が矛盾することによって示される。こうした証明を見ると、数学の本質的に、細かく値を代入して確かめることも重要であることが再認識させられる。
 | Proofs from THE BOOK 5,542円 Amazon |