高校数学解説

ベルトラン＝チェビシェフの定理を使った整数問題

ベルトラン＝チェビシェフの定理,素数,整数問題

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

はじめに

ご挨拶

こんにちは。
「nと2nの間には素数がある」―ベルトラン＝チェビシェフの定理という整数論の定理を聞いたことがあるでしょうか。

一見すると素朴な定理に思えるかもしれませんが，実は整数問題を解くのに偉大な武器になるということをご存知でしょうか。

先日，Geminiとの会話中に，この定理を主役とした整数問題への応用を2つ見つけたので，解説したいと思います！

ベルトラン＝チェビシェフの定理

まず，今回の主役であるベルトラン＝チェビシェフの定理について確認しましょう。

ベルトラン＝チェビシェフ (Bertrand–Chebyshev)

任意の自然数$n$に対して，ある素数$p$が存在して，$n< p\leq2n$を満たす。

この定理は，ベルトランが一般の$n$について予想として提起し，その後にチェビシェフによって解決されたことから，この名が付けられました。

定理自体の証明は，大掛かりなものとなってしまうため，今回は証明を扱いませんが，エルデシュによる初等的な証明も知られているので，ぜひ調べてみてください。

問題1：和が素数となる自然数

問題を考える

早速ですが，「和が素数となる自然数のペア」について考えてみましょう。（自然数は$1$から始まるものとします。）

例えば，自然数の組$(1,1)$や$(3,4)$は足したら素数になります。このような組は幾つでも作れますが，ここに条件を加えてみたらどうなるでしょうか。

次の問題を考えてみましょう。

$n$を自然数とする。自然数の切片$I_n=J_n=\{1,2,\dots,n\}$に対して，次を満たす集合$S\subset I_n\times J_n$は存在するか。

任意の$(i,j)\in S$に対して，$i+j$は素数である。
任意の異なる$(i,j),(i’,j’)\in S$に対して，$i\neq i’$かつ$j\neq j’$である。
任意の$k\in I_n$に対して，ある$(i,j)\in S$が存在して，$k=i$である。
任意の$l\in J_n$に対して，ある$(i,j)\in S$が存在して，$l=j$である。

これらの条件は複雑なので，例示して解説します。

$n=5$の例

例として，$n=5$のときで考えてみましょう。
まず，和が素数となるものを列挙してみます。すると，$(1,1)$,$(1,2)$,$(1,4)$,$(2,3)$,$(2,5)$,$(3,4)$と，その入れ替えが見つかります。

これらをいくつか集めた集合のうち，1つ目の自然数と2つ目の自然数がそれぞれ，被りなく$\{1,2,3,4,5\}$の全てが使われるようなものを求めたいです。

そこで，$4,5$に注目してみましょう。これらは先ほど挙げたペアのうちで，それぞれ$3,2$としかペアを組んでいません。なので，$(2,5),(3,4),(4,3),(5,2)\in S$となるしかありません。

残っているのは$1$ですが，これは自身とペアを組めば良いので，よって$n=5$のときは，$S=\{(1,1),(2,5),(3,4),(4,3),(5,2)\}$とすれば達成です。

大きい方のペアを作る

一般の$n$ではどうでしょうか。
素数の分布が正確にわかっていないので，「この数に対応するのはこれ」といったように，相方を求めるのは難しそうです。
そこで，ベルトラン＝チェビシェフの定理から導かれる以下のことに着目します。

$n$を任意の自然数とする。このとき，ある自然数$m,\,(1\leq m\leq n)$が存在して，$n+m$は素数になる。

ベルトラン＝チェビシェフの定理より，$n< p\leq2n$を満たす素数が存在する。$n,p$は自然数なので特に，$n+1\leq p\leq2n$である。
よって，$m=p-n$とすれば，$1\leq m\leq n$であり，$n+m$は素数となる。

この補題はほとんどベルトラン＝チェビシェフの定理を言い換えただけですが，実はこのことをさらに応用すると，次のことが示せます。

$n$を自然数とし，$I_n=J_n=\{1,2,\dots,n\}$を自然数の切片とする。このとき，ある非負整数$k,\,(0\leq k< n)$が存在して，次を満たす集合$S\subset (I_n\setminus I_k)\times(J_n\setminus J_k)$が存在する。

ある素数$p$が存在して，任意の$(i,j)\in S$に対して，$i+j=p$である。
任意の異なる$(i,j),(i’,j’)\in S$に対して，$i\neq i’$かつ$j\neq j’$である。
任意の$x\in I_n\setminus I_k$に対して，ある$(i,j)\in S$が存在して，$x=i$である。
任意の$y\in J_n\setminus J_k$に対して，ある$(i,j)\in S$が存在して，$y=j$である。

ただし，$I_0=J_0=\varnothing$とします。

この補題は問題1と似ていますが，異なる点が2つあります。
1つ目は，$I_n=\{1,2,\dots,n\}$が$I_n\setminus I_k=\{k+1,k+2,\dots,n\}$になっていることです。
そして2つ目は，$i+j$の値が固定されていることです。

このように変えることによって，ベルトラン＝チェビシェフの定理を用いて$S$を構成することができます。

補題2より，$n+m$が素数となるような$m,\,(1\leq m\leq n)$が存在する。ここで，補題3における$k,p$を，$k=m-1$,$p=m+n$ととる。
すなわち，$I_n\setminus I_k=J_n\setminus J_k=\set{m,m+1,\dots,n}$である。

すると，$S=\set{(m,n),(m+1,n-1),\dots,(n,m)}$は条件(i),(ii),(iii),(iv)全てを満たす。

実際に，$n=5$のときで確かめてみましょう。

$1\leq m\leq5$を満たして$5+m$が素数となるような自然数$m$は，$m=2$だけです。よって，$S=\set{(2,5),(3,4),(4,3),(5,2)}$とします。

すると，$2+5=3+4=4+3=5+2=7$であり，$S$の要素の1つ目の数と2つ目の数はそれぞれ，被りがなく，$\set{2,3,4,5}$を網羅できています。

数学的帰納法で示す

最後の仕上げをします。先に答えを言ってしまうと，問題1のような$S$は必ず存在します。このことを示していきます。

問題1（再掲）

$n$を任意の自然数とする。自然数の切片$I_n=J_n=\{1,2,\dots,n\}$に対して，次を満たす集合$S\subset I_n\times J_n$は必ず存在する。

任意の$(i,j)\in S$に対して，$i+j$は素数である。
任意の$(i,j),(i’,j’)\in S$に対して，$i\neq i’$かつ$j\neq j’$である。
任意の$k\in I_n$に対して，ある$(i,j)\in S$が存在して，$k=i$である。
任意の$l\in J_n$に対して，ある$(i,j)\in S$が存在して，$l=j$である。

補題3より，ある非負整数$k,(0\leq k< n)$が存在して，条件(i),(ii),(iii),(iv)全てを満たすような$S\subset (I_n\setminus I_k)\times(J_n\setminus J_k)$が存在する。
もし$k=0$であれば，補題3からすぐにこの定理4を導ける。なので，$1\leq k$のときを考える。

数学的帰納法で示す。
$n=1$のとき，$S={(1,1)}$とすれば，$1+1=2$であり，条件(i),(ii),(iii),(iv)全てを満たす。
$n\leq N$で成り立つと仮定し，$n=N+1$のときを考える。
補題3を用いると，条件(i),(ii),(iii),(iv)全てを満たすような$S\subset I_k\times J_k$が存在することの証明に帰着できる。
これは，$n=k$のときに相当し，特に$k< n$なので，帰納法の仮定よりこのような$S$は存在する。

よって，任意の$n$について，条件(i),(ii),(iii),(iv)を満たすような集合$S$が必ず存在する。

ということで，$S$が必ず存在することを示すことができました！

グラフ理論を用いた表現

問題1は，整数以外の枠組みにおいても記述することができます。

グラフ理論を用いると，先ほどの問題1および定理4は，2部グラフの完全マッチング問題と捉えることができます。
定理4を言い換えてみましょう。

$n$を自然数とする。$X_n=\set{x_1,x_2,\dots,x_n}$,$Y_n=\set{y_1,y_2,\dots,y_n}$とし，$E_n=\set{\set{x_i,y_j}\mid x_i\in X_n,\,y_j\in Y_n,\,i+j=\text{素数}}$とする。このとき，2部グラフ$G_n=(X_n,Y_n,E_n)$には完全マッチングが存在する。

2部グラフとは，頂点集合を互いに辺で繋がらない2つの集合に分割できるグラフのことです。
そして，完全マッチングとは，互いに辺の端点を共有しないような辺集合の部分集合であるマッチングのうち，全ての頂点がなんらかの端点となっているもののことです。

集合の分割を用いた表現

問題1および定理4とは，また少し違った表現を考えてみます。ペアを組むことを，集合の分割に置き換えて次のようにします。

$n$を正の偶数とし，$I_n=\set{1,2,\dots,n}$を自然数の切片とする。このとき，$I_n$の分割$\mathcal{P}$であって，次を満たすものが存在する。

任意の$s\in\mathcal{P}$に対して，$s$の要素の個数は$2$である。
任意の$s\in\mathcal{P}$に対して，$s$の要素の和は素数である。

分割とは，以下のように定義されるものです。

集合$X$に対して，$\mathcal{P}$が$X$の分割であるとは，次の3つを満たすことをいう。

$\varnothing\notin\mathcal{P}$である。
$\bigcup_{s\in\mathcal{P}}s=X$である。
任意の$s_1,s_2\in\mathcal{P}$に対して，$s_1\cap s_2=\varnothing$である。

つまり，重複がないように，全ての要素をいくつかに振り分けたものが分割です。

この定理6についても，例を見てみましょう。
$n=8$とし，$\mathcal{P}=\set{\set{1,2},\set{3,4},\set{5,8},\set{6,7}}$とします。
すると，$\mathcal{P}$は$I_n$の分割であり，2個ずつに分けられていて，和が全て素数になっているので，条件(i),(ii)を満たすことがわかります。

では，定理6を証明していきます。証明方法は先ほどの定理4とほぼ一緒です。

数学的帰納法で示す。

$n=2$のとき，$\mathcal{P}=\set{\set{1,2}}$とすれば，条件(i),(ii)全てを満たす。

$n\leq 2N$で成り立つと仮定し，$n=2(N+1)$のときを考える。
ベルトラン＝チェビシェフの定理より，$n< p\leq2n$を満たす素数$p$が存在する。特に，$2\leq n$であるので，$p<2n$であり，$p$は奇素数である。

ここで，そのような$p$に対して，$m=p-n\geq1$とおき，$n$は偶数，$m$は奇数であることに注意して，
$$ S=\left\{\{m,n\},\{m+1,n-1\},\dots,\left\{\frac{p-1}{2},\frac{p+1}{2}\right\}\right\}$$
とする。すると，この$S$に属する任意の集合の要素の個数は2であり，和は素数になる。

集合$\{m,m+1,\dots,n\}$において，定理6の条件(i),(ii)を満たす分割$S$が存在し，$I_0=\varnothing$とすれば，帰納法の仮定より$I_{m-1}$においても，条件(i),(ii)を満たすような分割$\mathcal{P}'$が存在する。
$\mathcal{P}=S\cup\mathcal{P}'$とすれば，この$\mathcal{P}$は集合$I_n$における条件(i),(ii)を満たす分割となる。

ということで，問題1はこれにて終了です！

問題2：階乗の一致

問題を考える

続いて，次のことについて考えてみましょう。
\begin{equation} \begin{split} 1!&=1!\\ 1!\cdot3!&=(1+2)!\\ 1!\cdot3!\cdot5!&=(1+2+3)!\\ 1!\cdot3!\cdot5!\cdot7!&=(1+2+3+4)! \end{split} \end{equation}
これらは有名な偶然の一致で，残念ながら，$1!\cdot3!\cdot5!\cdot7!\cdot9!\ne(1+2+3+4+5)!$となってしまいます。しかし，ここまで一致するのはすごいですね。
ここで，次の問題を考えてみましょう。

$n$を自然数とする。次の$a_n$が整数となる$n$を全て求めよ。
$$ a_n=\dfrac{\prod_{k=1}^{n}(2k-1)!}{\left(\sum_{k=1}^{n}k\right)!}$$

先より，$a_1=a_2=a_3=a_4=1$となりますが，$a_5=\dfrac{144}{143}$となって整数ではありません。
また，$a_6=\dfrac{4320}{4199},\,a_7=\dfrac{103680}{96577},\,a_8=\dfrac{130636800}{113537407}$となっていくので，$n\geq5$では整数にならないのではないかと予想ができます。

極限による推測

$a_1,a_2,\dots,a_8$の計算結果から，$a_n$は$n$の増加に伴って広義単調に増加し，$n\to\infty$での極限で正の無限大に発散するような感じがしますが，もし収束するのであれば，不等式ではさみこむことができるので，極限を調べてみます。

スターリングの公式：$\log(n!)=n\log{n}-n+O(\log{n})$による階乗の近似と積分近似を用いると，
\begin{equation} \begin{split} \sum_{k=1}^n\log((2k-1)!)&=\sum_{k=1}^n\left\{(2k-1)\log(2k-1)-(2k-1)+O(\log k)\right\},\\ &=\left\{\frac{1}{4}(2n-1)^2\log(2n-1)-\frac{1}{8}(2n-1)^2+C\right\}-n^2+O(n\log{n}),\\ &=n^2\log{n}+\left(\log2-\frac{3}{2}\right)n^2+O(n\log{n}).\\\\ \log\left(\left(\dfrac{n(n+1)}{2}\right)!\right)&=\dfrac{n(n+1)}{2}\log{\dfrac{n(n+1)}{2}}-\dfrac{n(n+1)}{2}+O\left(\log{\left(\dfrac{n(n+1)}{2}\right)}\right),\\ &=\frac{n^2 + n}{2}\left(2\log{n}-\log2+\frac{1}{n}\right)-\frac{n^2}{2}+O(n\log{n}),\\ &=n^2\log{n}-\left(\frac{\log2+1}{2}\right)n^2+O(n\log{n}).\\\\ \log{a_n}&=\sum_{k=1}^n\log((2k-1)!)-\log\left(\left(\frac{n(n+1)}{2}\right)!\right),\\ &=\left\{\left(\log2-\frac{3}{2}\right)-\left(-\frac{\log 2 + 1}{2}\right)\right\}n^2+O(n\log{n}),\\ &=\left(\frac{3}{2}\log2-1\right)n^2+O(n\log{n}). \end{split} \end{equation}
となり，$2\sqrt{2}>e$となることから，$a_n\xrightarrow{n\to\infty}\infty$と発散してしまうことが分かりました。なので，整数論的な観点からのアプローチを試みることとします。

分母に着目する

$a_n$が整数にならないということは，$a_n$の分母が分子を割り切らないということであるので，それぞれの素因数に着目してみます。
$$a_5:144=2^4\times3^2,\;143=11\times13.$$
$$a_6:4320=2^5\times3^3\times5,\;4199=13\times17\times19.$$
$$a_7:103680=2^8\times3^4\times5,\;96577=13\times17\times19\times23.$$
$$a_8:130636800=2^{10}\times3^6\times5^2\times7,\;113537407=17^2\times19\times23\times29\times31.$$
すると，分子には比較的小さい素因数が，分母には比較的大きい素因数があるということが分かります。
それもそのはずで，分子には高々$(2n-1)$までの自然数の積しか出てきていないのに対して，分母には$\dfrac{n(n+1)}{2}$までの自然数の積が出てくるので，分母の方が掛けられる自然数の範囲が広く，その分，分子にはない素因数も含むだろうと考えられます。

つまり，$2n-1< p\leq\dfrac{n(n+1)}{2}$を満たす素数$p$が存在するかを調べればよいということが分かります。ベルトラン＝チェビシェフの定理が適用できそうな形なので，それを用いて示していきます。

$n\geq5$を任意の自然数とする。このとき，ある素数$p$が存在して，次を満たす。
$$ 2n-1< p\leq\dfrac{n(n+1)}{2}$$

$n=5$のとき，$p=11$とすれば与式を満たす。
$n=6$のとき，$p=13$とすれば与式を満たす。

$n\geq7$のとき，ベルトラン＝チェビシェフの定理より，$2n-1< p<4n-2$を満たす素数$p$が存在する。$4n-2$と$\dfrac{n(n+1)}{2}$について，
$$ \frac{n(n+1)}{2}-(4n-2)=\frac{1}{2}\left(n-\frac{7}{2}\right)^2-\frac{33}{8}$$
は$n\geq7$で常に正であるので，$4n-2<\dfrac{n(n+1)}{2}$である。
すなわち，任意の$n\geq7$に対して，$2n-1< p<4n-2$を満たすような素数$p$は常に存在し，この$p$は以下も満たす。
$$ 2n-1< p\leq\dfrac{n(n+1)}{2}$$
よって，$n=5,6$のときも合わせれば，任意の$n\geq5$で与式を満たす素数$p$が存在する。