「nと2nの間には素数が存在する」の初等的な証明（前編）

フランスの数学者ベルトランは素数表を観察する中で次の予想を立てました。

$n=1, 2, 3, \dots$で確認すると

• $n=1$: $1 < 2 \leq 2$より素数$2$が存在
• $n=2$: $2 < 3 \leq 4$より素数$3$が存在
• $n=3$: $3 < 5 \leq 6$より素数$5$が存在
• $n=4$: $4 < 7 \leq 8$より素数$7$が存在

とたしかに素数が存在します。

ベルトランは$n \leq 3\times 10^6$で予想が正しいことを検証しましたが任意の自然数で成立することを示すには至りませんでした。ベルトランの予想から5年後、チェビシェフがこの予想を肯定的に解決し「ベルトラン・チェビシェフの定理」と呼ばれます。

チェビシェフの証明はガンマ関数を用いた高度なものでしたが、放浪の天才数学者として有名なエルデシュが高校生の時に初等的な証明を発見しました。その証明が「Proofs from THE BOOK」^[1]エルデッシュは無神論者でしたが、「すべての定理、理論が書かれた本」の存在を信じており”THE … Continue reading（邦訳「天書の証明」）に載っています。また、数研通信70号に一松信先生が「$n$と$2n$の間に素数がある」という記事で解説されておりそれぞれを参考に前編、後編の2回に分けエルデシュによる証明を紹介します。

一松信先生も記事のなかで

実力のある高校生なら十分に理解できる証明で，知っていて損はしないと思いますのでここに紹介します。

とコメントされている通り高校生でも十分理解できる内容なので証明を一緒に追ってもらえればと思います。

証明のアウトライン

エルデシュは二項係数の中央の値${}_{2n}C_n$を素因数分解

${}_{2n}C_n = p_1^{a_1}p_2^{a_2}\cdot \cdots \cdot p_k^{a_k}$

した時の素因数$p_i$とその指数$a_i$を考察し次の性質を導きます。

• 各因数は$p_i^{a_i} \leq 2n$と上から押さえられる。
• $p_i > \sqrt{2n}$ならば因数は$p_i^1$の形になる。
• $p_i$は$\left[2, \frac{2}{3}n\right], \left(n, 2n\right]$の範囲にしか現れない。

ここから${}_{2n}C_n$は

$\displaystyle {}_{2n}C_n = \prod_{p_i \leq \sqrt{2n}} p_i^{a_i}\prod_{\sqrt{2n} < p_i \leq \frac{2}{3}n} p_i\prod_{n < p_i \leq 2n} p_i$

とかけ、$\displaystyle \prod_{n < p_i \leq 2n} p_i$の大きさを評価することで

$n$と$2n$の間には素数が一定数存在する

という結論を導くことができます。

素因数$p_i$と指数$a_i$の性質

二項係数${}_{2n}C_n=\frac{(2n)!}{n!n!}$なのでまず$n!$の素因数$p$の指数に関する補題を示します。

この補題は「ルジャンドルの定理」として知られており、例えば「高校数学の美しい物語」さんに分かりやすい証明があります。

この補題から${}_{2n}C_n=\frac{(2n)!}{n!n!}$の素因数$p_i$の指数$a_i$は分子$(2n)!$の$p_i$の指数から分母$n!n!$の指数を引いて

$\begin{eqnarray} a_i &=& \sum_{k = 1}^{\lfloor \log_{p_i} 2n \rfloor}\left(\left\lfloor \dfrac{2n}{p^k} \right\rfloor – 2\left\lfloor \dfrac{n}{p^k} \right\rfloor \right) \end{eqnarray}$

と書けます。一般に実数$x \in \mathbb{R}$に対して$x = \lfloor x \rfloor + c(0 \leq c < 1)$とかけ

$\begin{eqnarray} \lfloor 2x \rfloor – 2\lfloor x \rfloor &=& \lfloor 2c \rfloor \\ &\leq & 1 \end{eqnarray}$

なので$x_k = \frac{n}{p^k}$とおくと

$\begin{eqnarray} a_i &=& \sum_{k = 1}^{\lfloor \log_{p_i} 2n \rfloor}\left(\lfloor 2x_k \rfloor – 2\lfloor x_k \rfloor\right) \\ &\leq& \lfloor \log_{p_i} 2n \rfloor \\ &\leq& \log_{p_i} 2n \end{eqnarray}$

が成立します。これより

$\begin{eqnarray} p_i^{a_i} &\leq & p_i^{\log_{p_i} 2n} \\ &\leq & 2n \end{eqnarray}$

となります。また、$p_i > \sqrt{2n}$の時

$\begin{eqnarray} a_i &\leq& \log_{p_i} 2n \\ &=& \dfrac{\log 2n}{\log p_i} \\ &<& 2 \end{eqnarray}$

より$a_i=1$となることもわかります。まとめると以下になります。

${}_{2n}C_n$の素因数$p_i$がとり得る範囲

エルデッシュの証明の根幹をなす次の性質を示します。

${}_{2n}C_n=\frac{(2n)!}{n!n!}$の分子、分母に現れる$p_i$の回数を数えてみます。

$\frac{2}{3}n < p_i \leq n$の場合、$p_i \leq n < 2p_i \leq 2n < 3p_i$なので$p_i$を約数に持つ数は

• 区間$[1, n]$: $p_i$のみ
• 区間$[1, 2n]$: $p_i$と$2p_i$

となり${}_{2n}C_n=\frac{(2n)!}{n!n!}$の分子、分母でちょうど2回ずつ現れ約分されるので素因数に持つことはありません。

具体例でみる各性質

エルデッシュが導いた

を具体例を通じて確認してみましょう。$n=15$の場合

$\begin{eqnarray} {}_{30}C_{15} &=& \dfrac{30!}{15!15!} \\ &=& 2^4\cdot 3^2\cdot 5\cdot 17\cdot 19\cdot 23\cdot 29 \end{eqnarray}$

と因数分解でき

• 各因数について$p_i^{a_i} \leq 30$
• $p_i > \sqrt{30}=5.47\ldots$つまり$7$以上の素因数の指数は$1$
• $p_i \notin \left(10, 15\right]$つまり素因数$11, 13$を含まない

と確かに性質が成立していることがわかります。

後編ではこれらの性質を使って$\displaystyle \prod_{n < p_i \leq 2n} p_i$の大きさを評価し

$n$と$2n$の間には素数が一定数存在する

という結論を導いていきます。

参考文献

• 「Proofs from THE BOOK」（邦訳「天書の証明」）: Chapter 2, Bertrand’s postulate
• 一松 信, 「nと2nの間に素数がある」（数研通信70号）
• 栃折 成紀, 「「nと2nの間に素数がある」の証明を考える」（数研通信76号）