2018-09-04

ベルトランの仮説と素数定理に関するエルデシュの証明

Bertrandの仮説の主張は次のようなものでした。

Bertrandの仮説 (1845) 任意の自然数 $n$ に対して、 $n < p \leq 2n$ を満たすような素数 $p$ が少なくとも一つ存在する。

Bertrandの仮説で考察している区間 $(n, 2n]$ を $\varepsilon > 0$ に対する $(n, (1+\varepsilon)n]$ に拡張することを考えたとき、次の定理が成立します。

定理１ 任意の $\varepsilon > 0$ に対して $n_0(\varepsilon)$ が存在して、 $n\geq n_0(\varepsilon)$ であれば $n < p \leq (1+\varepsilon)n$ を満たすような素数 $p$ が少なくとも一つ存在する。

ただし、 $n_0(\varepsilon)$ の存在性のみを保証しているこの定理はBertrandの仮説の完全な一般化ではありません。Bertrandの仮説は $n_0(1)=1$ と取れることまで主張しています。

$n_0(\varepsilon)$ として取り得る最小の整数値を考えることにしたとき、幾つかの $\varepsilon$ に対する $n_0(\varepsilon)$ が歴史的に求められてきました。

例えば、

J. Nagura, On the interval containing at least one prime number, Proc. Japan Acad. Ser. A 28 (1952), 177–181.

では $n_0(1/5)=25$ が示されています。また、仮面ライダービルドの第４８話では $n_0(1/8)=48$ が紹介されています。Dusartの結果を利用して、ここでは次の定理を紹介しておきます。

定理 (Dusart) $n_0(1/100)=2479$ である。

証明. Dusart

P. Dusart, The $k$ th prime is greater than $k(\log k + \log \log k − 1)$ for $k \geq 2$ , Math. Comp. 68 (1999), 411–415.

で $x \geq 3725$ であれば

$\displaystyle x \leq p \leq x\left(1+\frac{1}{2\log^2x}\right)$

の間に少なくとも一つは素数が存在することが示されており、 $1+\frac{1}{2\log^23275}=1.0076...$ であることから $n_0(0.01) \leq 3275$ であることがわかる。 $2478\times 1.01$ の整数部分は $2502$ であるが、 $2477$ の次の素数は $2503$ なので、 $n_0(0.01) \geq 2479$ でなければならない。あとは素数列

$\begin{align} &2503, 2521, 2543, 2557, 2579, 2593, 2617, 2633, 2659, 2683, 2707,\\ &2731, 2753, 2777, 2803, 2819, 2843, 2861, 2887, 2909, 2927, 2953, \\ &2971, 2999, 3023, 3049, 3079, 3109, 3137, 3167, 3191, 3221, 3251, \\ &3271, 3299\end{align}$

をみれば $n_0(0.01)=2479$ が確定する。 Q.E.D.

さて、定理１は十分大きい $n$ に対して区間 $(n, (1+\varepsilon)n]$ が少なくとも一つの素数を含むことを主張していますが、より強く任意の正整数 $k$ について、十分大きい $n$ に対して区間 $(n, (1+\varepsilon)n]$ が少なくとも $k$ 個の素数を含むこともいえます。実際、次が成り立ちます。

定理２ 任意の $\varepsilon > 0$ に対して或る $\delta(\varepsilon) > 0, x_0(\varepsilon) > 0$ が存在して、 $x \geq x_0(\varepsilon)$ であれば

$\displaystyle \pi\left( (1+\varepsilon)x\right)-\pi(x) > \frac{\delta(\varepsilon)x}{\log x}$

が成り立つ。ここで、 $\pi(x)$ は素数個数関数。

この定理自体は素数定理から即座に従いますが、素数定理の初等的証明と深い関係があります。

素数定理の初等的証明（予告編） - INTEGERS

において素数定理の初等的証明に関するSelbergとErdősの関係について少し解説しました。彼らの論文に記載の内容をもとに、もう少し詳細に述べると

SelbergがSelbergの漸近公式を証明
ErdősがSelbergの漸近公式を用いた定理２の証明を発見
そのErdősのアイデアとSelbergの漸近公式と定理２を用いてSelbergが最初の素数定理の初等的証明に成功
Selbergが定理２の証明を簡略化
Erdős-Selbergが素数定理の初等的証明を簡略化(証明のアイデアは必要であるが、定理２は不要となる)
Selbergは上(下)極限の概念の使用も排除したSelbergの漸近公式からの素数定理の新しい導出法を発見
二人は独立に論文を出版(!!)

のようになっているようです。6. のSelbergによる証明は上記記事において既に解説しました。この記事では

P. Erdős, On a new method in elementary number theory which leads to an elementary proof of the prime number theorem, Proc. Nat. Acad. Scis. U.S.A. 35 (1949), 374–384.

に基づいて、2. の証明を解説しようと思います*1。

Erdősによる定理２の証明

漸近挙動は原則 $x \to \infty$ で考える。 $\vartheta(x)$ をChebyshev関数とするとき、ここで使用した不等式を利用することによって定理２は次の定理と同値であることがわかる。

定理３ 任意の $\varepsilon > 0$ に対して或る $\delta(\varepsilon) > 0, x_0(\varepsilon) > 0$ が存在して、 $x \geq x_0(\varepsilon)$ であれば

$\displaystyle \vartheta\left( (1+\varepsilon)x\right)-\vartheta(x) > \delta(\varepsilon)x$

が成り立つ。

次の二つの事実は前提知識として用いる。

Chebyshevの定理 $\displaystyle 0 < \liminf_{x \to \infty}\frac{\vartheta(x)}{x} \leq \limsup_{x \to \infty}\frac{\vartheta(x)}{x} \leq 1.5$ が成り立つ。実際、全ての $x \geq 2$ に対して $\vartheta(x) \leq 1.5x$ が成り立つ。

証明. チェビシェフの定理 - INTEGERS Q.E.D.

Selbergの漸近公式 次の漸近公式が成り立つ。

$\displaystyle \sum_{p \leq x}\log^2 p+\sum_{pq \leq x}\log p\log q=2x\log x+O(x).$

証明. 素数定理の初等的証明（Selbergの漸近公式編） - INTEGERSにおける(1)である。 Q.E.D.

補題１ $x_2 > x_1$ に対して

$\vartheta(x_2)-\vartheta(x_1) \leq 2(x_2-x_1) + O\left(\frac{x_2}{\log x_2}\right)$

が成り立つ。

証明. Selbergの漸近公式から導出できる(ここを参照)。 Q.E.D.

以下、定理３を背理法で証明するため、或る $c > 0$ が存在して、 $x \to \infty$ という状態において

$\vartheta\left( (1+c)x\right)-\vartheta(x)=o(x) \tag{1}$

が成り立つようないくらでも大きい $x$ が存在すると仮定する*2。 $C$ をこのような $c$ の上限とする。このとき、 $C < \infty$ である。理由: Chebyshevの定理より、 $a, A>0$ が存在して、十分大きい $x$ に対して $ax \leq \vartheta(x) \leq Ax$ が成り立つ。このとき、

$\displaystyle \vartheta\left( (1+\varepsilon)x\right)-\vartheta(x) \geq \{(1+\varepsilon)a-A\}x$

が成り立ち、ある程度大きい $\varepsilon > 0$ に対しては(1)の状況にできないことがわかる。

実際には、 $C$ は最大値として実現している。

補題２ $x \to \infty$ で

$\displaystyle \vartheta\left( (1+C)x\right)-\vartheta(x) = o(x)$

となるようないくらでも大きい $x$ が存在する。

証明. $\varepsilon' > 0$ を任意にとり、 $c > C-\frac{\varepsilon'}{2}$ かつ(1)を満たすような $c$ をとる。補題１と(1)より、いくらでも大きい $x$ が存在して

$\begin{align} \vartheta\left( (1+C)x\right) - \vartheta(x) &= \vartheta\left( (1+C)x\right)-\vartheta\left( (1+c)x\right)+\vartheta\left( (1+c)x\right)-\vartheta(x) \\ &\leq 2(C-c)x+o(x) < \varepsilon' x+o(x)\end{align}$

が成り立つ。つまり、 $\vartheta\left( (1+C)x\right) - \vartheta(x) < 2\varepsilon'x$ となるような $x$ が存在する。よって、 $\varepsilon'$ の任意性から結論が得られる。 Q.E.D.

補題３ 補題２における無数の $x$ について、次の漸近公式が成り立つ。

$\displaystyle \sum_{p \leq (1+C)x}\log p\left\{\vartheta\left( (1+C)\frac{x}{p}\right)-\vartheta\left(\frac{x}{p}\right)\right\}=2Cx\log x+o(x\log x)$

証明. Selbergの漸近公式の差を取ることによって

$\displaystyle \sum_{x < p \leq (1+C)x}\log^2 p+\sum_{x < pq \leq (1+C)x}\log p\log q = 2Cx\log x+o(x\log x)$

が得られる。補題２より

$\displaystyle \sum_{x < p \leq (1+C)x}\log^2 p \leq (1+C)\log x\left\{\vartheta\left( (1+C)x\right)-\vartheta(x)\right\}=o(x\log x)$

であり、

$\begin{align}\sum_{x < pq \leq (1+C)x}\log p\log q&=\sum_{p \leq (1+C)x}\log p\sum_{\frac{x}{p} < q\leq \frac{(1+C)x}{p}}\log q\\ &=\sum_{p \leq (1+C)x}\log p\left\{\vartheta\left( (1+C)\frac{x}{p}\right)-\vartheta\left(\frac{x}{p}\right)\right\}\end{align}$

と変形できるので所望の漸近公式が示された。 Q.E.D.

これを利用して $(1+C)x$ 以下の素数をbad primeとgood primeに分ける。

補題４ 補題２における無数の $x$ を考える。 $(1+C)x$ 以下の素数の集合を $P_x$ とする。このとき、 $P_x=B_x \sqcup G_x$ と二分する集合 $B_x, G_x$ であって

$\displaystyle \sum_{p \in B_x}\frac{\log p}{p} = o(\log x),\tag{2}$

$\displaystyle \vartheta\left( (1+C)\frac{x}{p}\right) - \vartheta\left(\frac{x}{p}\right) = 2C\frac{x}{p}+o\left(\frac{x}{p}\right)\quad \text{for} \quad p \in G_x \tag{3}$

を満たすようなものが存在する。

証明. 背理法で証明する。つまり、いくらでも大きい $x$ が存在して、そのような $x$ について、 $x \to \infty$ という状況で、 $\frac{\log p}{p}$ の和が $o(\log x)$ とならないだけ多くの $(1+C)x$ 以下の素数 $p$ に対して(3)の漸近公式が成り立たないとする。必要であればそのような素数達の部分集合をとることによって、或る $A_x \subset P_x$ , $b_1, b_2 > 0$ が存在して

$\displaystyle \sum_{p \in A_x}\frac{\log p}{p} \sim b_1 \log x \tag{4}$

および

$\displaystyle \vartheta\left( (1+C)\frac{x}{p}\right) - \vartheta\left(\frac{x}{p}\right) < (2C-b_2)\frac{x}{p}\quad \text{for} \quad p \in A_x \tag{5}$

が成り立つと仮定してよい( (3)の否定を考えて(5)で十分なことには補題１を用いている)。(4)とMertensの第一定理から

$\displaystyle \sum_{p \in P_x \setminus A_x}\frac{\log p}{p} \sim (1-b_1)\log x \tag{6}$

が成り立つため、補題１、(4)、(5)、(6)を用いると

$\begin{align} &\sum_{p \leq (1+C)x}\log p\left\{\vartheta\left( (1+C)\frac{x}{p}\right)-\vartheta\left(\frac{x}{p}\right)\right\} \\ &= \sum_{p \in A_x}\log p\left\{\vartheta\left( (1+C)\frac{x}{p}\right)-\vartheta\left(\frac{x}{p}\right)\right\}+ \sum_{p \in P_x \setminus A_x}\log p\left\{\vartheta\left( (1+C)\frac{x}{p}\right)-\vartheta\left(\frac{x}{p}\right)\right\} \\ &< b_1(2C-b_2)x\log x+2C(1-b_1)x\log x+o(x\log x) \\ &=(2C-b_1b_2)x\log x+o(x\log x)\end{align}$

となって補題３に矛盾する。ここで、和 $\sum_{p \in P_x \setminus A_x}$ の部分に補題１を適用して得られる誤差項が $o(x\log x)$ となることには以前証明した漸近公式を使えばよい。 Q.E.D.

補題５ $t > 0$ を任意にとって固定する(いくらでも小さくてよい)。補題２における無数の $x$ を考える。このとき、 $x$ が十分大きければ、補題４における $G_x$ の元 $p_1 < p_2 < \cdots < p_k$ であって $10p_1 < p_k$ および

$(1+t)p_i < p_{i+1} < (1+C)(1+t)^2p_i \quad \text{for} \quad 1 \leq i \leq k-1$

が成り立つようなものが存在する。

証明. 補題２で存在する $x$ であって(適宜)十分大きいものを考える。また、 $B > 0$ を十分大きい数とする。 $0 \leq r \leq \left[\frac{\log x}{2\log B}\right]-1$ に対して、 $I_r:=(B^{2r}, B^{2r+1}) \subset (0, x)$ とする。このとき、 $r$ に依存しない或る $c_1 > 0$ が存在して

$\displaystyle \sum_{p \in I_r}\frac{\log p}{p} > c_1 \tag{7}$

が成り立つ。理由:

$\displaystyle \sum_{p \in I_r}\frac{\log p}{p} \geq \frac{1}{B^{2r+1}}\left\{\vartheta(B^{2r+1})-\vartheta(B^{2r})\right\}$

であるが、Chebyshevの定理より $B$ が十分大きいことから $\vartheta(By)-\vartheta(y) > c_1'y$ が十分大きい $y$ に対して成立するので、 $c_1:=c_1'/B$ と取れることがわかる。

$\displaystyle \#\{r \mid I_r \subset B_x\}=o(\log x) \tag{8}$

である。理由: $c_2 > 0$ に対して

$\displaystyle \#\{r \mid I_r \subset B_x\} > c_2\log x$

であれば、(7)より $\displaystyle \sum_{p \in B_x}\frac{\log p}{p} > c_1c_2\log x$ となって、(2)に矛盾する。 (8)より、少なくとも $\frac{\log x}{4\log B}$ 以上の $r$ について $I_r \cap G_x\neq \varnothing$ である。そのような $r$ について $p_1^{(r)}$ を $I_r \cap G_x$ の最小素数とする。今、そのような全ての $r$ について

$(1+t)p_i^{(r)} < p_{i+1}^{(r)} < (1+C)(1+t)^2p_i^{(r)} \tag{9}$

が $1 \leq i \leq j-1$ で成り立つような $p_j^{(r)} \leq 10p_1^{(r)}$ である $G_x$ の元 $p_1^{(r)} < \cdots < p_j^{(r)}$ が存在するが、 $i=j$ で(9)が成立するような $p_{j+1}^{(r)}$ が存在しないと仮定しよう( $j$ は $r$ 依存)。このとき、

$\displaystyle J^{(r)}:=\left[(1+t)p_j^{(r)}, (1+C)(1+t)^2p_j^{(r)}\right]$

とすると $J^{(r)} \subset B_x$ である。 $z=(1+t)p_j^{(r)}$ とおくと、

$\displaystyle \sum_{p \in J^{(r)}}\log p = \vartheta\left( (1+C)(1+t)z\right)-\vartheta(z)$

であり、 $(1+C)(1+t) > 1+C$ であるから、 $C$ の最大性より或る $c_3$ が存在して

$\displaystyle \sum_{p \in J^{(r)}}\log p > c_3(1+C)(1+t)^2p_j^{(r)}$

が成り立つ( $c_3$ は $C, t$ 以外には依存しない)。よって、

$\displaystyle \sum_{p \in J^{(r)}}\frac{\log p}{p} > c_3 \tag{10}$

が成り立つ。さて、 $p_j^{(r)} \leq 10p_1^{(r)} \leq 10B^{2r+1}$ および $10(1+C)(1+t)^2 < B$ (と $B$ をとっておくことに)より

$(1+C)(1+t)^2p_j^{(r)} < B^{2r+2}$

なので、 $J^{(r)} \subset (B^{2r}, B^{2r+2})$ である。よって、少なくとも $\frac{\log x}{4\log B}$ 以上の $r$ 達 $r_1, r_2, \dots$ について、 $J^{(r_1)}, J^{(r_2)}, \dots$ は重なりがない。従って、(10)より

$\displaystyle \sum_{p \in B_x}\frac{\log p}{p} > \frac{c_3\log x}{4\log B}$

が得られた。これは(2)から(十分大きい $x$ については)許容されていない。よって、背理法により主張が示された。 Q.E.D.

補題５の状況の $x$ および $p_1 < p_2 < \cdots < p_k$ をとる。 $\frac{x}{p_{i}} < (1+C)\frac{x}{p_{i+1}}$ であるような $i$ については

$\displaystyle \vartheta\left(\frac{x}{p_i}\right)-\vartheta\left(\frac{x}{p_{i+1}}\right)=2\left(\frac{x}{p_i}-\frac{x}{p_{i+1}}\right)+o\left(\frac{x}{p_i}\right) \tag{11}$

が成り立つ。理由: 成り立たないと仮定する。このとき、補題１より $d_1 > 0$ が存在して

$\displaystyle \vartheta\left(\frac{x}{p_i}\right)-\vartheta\left(\frac{x}{p_{i+1}}\right) < (2-d_1)\left(\frac{x}{p_i}-\frac{x}{p_{i+1}}\right) \tag{12}$

となる。 $p_{i+1} \in G_x$ より

$\displaystyle \vartheta\left( (1+C)\frac{x}{p_{i+1}}\right)-\vartheta\left(\frac{x}{p_{i+1}}\right) = 2C\frac{x}{p_{i+1}}+o\left(\frac{x}{p_{i+1}}\right)$

なので、(12)と合わせて

$\displaystyle \vartheta\left( (1+C)\frac{x}{p_{i+1}}\right) - \vartheta\left(\frac{x}{p_i}\right) > 2C\frac{x}{p_{i+1}}+o\left(\frac{x}{p_{i+1}}\right)-(2-d_1)\left(\frac{x}{p_i}-\frac{x}{p_{i+1}}\right)$

となる。 $d_2 > 0$ が存在して

$\displaystyle 2C\frac{x}{p_{i+1}}-(2-d_1)\left(\frac{x}{p_i}-\frac{x}{p_{i+1}}\right) > (2+d_2)\left\{(1+C)\frac{x}{p_{i+1}}-\frac{x}{p_i}\right\} \tag{13}$

が成り立てば補題１に矛盾する。(13)は

$\displaystyle -d_1\frac{x}{p_{i+1}}+d_1\frac{x}{p_i} > d_2(1+C)\frac{x}{p_{i+1}}-d_2\frac{x}{p_i}$

すなわち、

$\displaystyle p_{i+1} > \left(1+\frac{d_2}{d_1+d_2}C\right)p_i$

と同値である。 $p_{i+1} > (1+t)p_i$ なので、 $d_2$ を十分小さく取ればこれは成立する。 $i=1$ に対する(11)と $p_1 \in G_x$ より成立する式

$\displaystyle \vartheta\left( (1+C)\frac{x}{p_1}\right)-\vartheta\left(\frac{x}{p_1}\right)=2C\frac{x}{p_1}+o\left(\frac{x}{p_1}\right)$

を組み合わせることにより、

$\displaystyle \vartheta\left( (1+C)\frac{x}{p_1}\right)-\vartheta\left(\frac{x}{p_2}\right) = 2\left\{(1+C)\frac{x}{p_1}-\frac{x}{p_2}\right\}+o\left(\frac{x}{p_1}\right) \tag{14}$

が得られる。 $(1+C)\frac{x}{p_{i+1}} \leq \frac{x}{p_i}$ であるような $i$ については

$\displaystyle \vartheta\left(\frac{x}{p_i}\right)-\vartheta\left(\frac{x}{p_{i+1}}\right)\geq 1.9\left(\frac{x}{p_i}-\frac{x}{p_{i+1}}\right) \tag{15}$

が成り立つ。理由: $p_{i+1} \in G_x$ なので

$\displaystyle \vartheta\left(\frac{x}{p_i}\right)-\vartheta\left(\frac{x}{p_{i+1}}\right) \geq \vartheta\left( (1+C)\frac{x}{p_{i+1}}\right)-\vartheta\left(\frac{x}{p_{i+1}}\right) =2C\frac{x}{p_{i+1}}+o\left(\frac{x}{p_{i+1}}\right)$

と評価できる。よって、

$\displaystyle 2C\frac{1}{p_{i+1}} > 1.9\left(\frac{1}{p_i}-\frac{1}{p_{i+1}}\right)$

が成り立てばよいが、 $\frac{1}{p_i} < (1+C)(1+t)^2\frac{1}{p_{i+1}}$ なので

$2C > 1.9(2t+t^2+C(1+t)^2)$

がいえればよい。右辺は $t \to 0$ で $1.9C$ に収束するので、十分小さい $t$ についてこれは成立している。 $i=1$ の場合の(15)に $p_1 \in G_x$ より成立する式

$\displaystyle \vartheta\left( (1+C)\frac{x}{p_1}\right)-\vartheta\left(\frac{x}{p_1}\right) > 1.9C\frac{x}{p_1}$

を合わせることによって

$\displaystyle \vartheta\left( (1+C)\frac{x}{p_1}\right)-\vartheta\left(\frac{x}{p_2}\right) > 1.9\left\{(1+C)\frac{x}{p_1}-\frac{x}{p_2}\right\} \tag{16}$

が得られる。(14)または(16)に(11)または(15)をtelescopingすると

$\displaystyle \vartheta\left( (1+C)\frac{x}{p_1}\right) - \vartheta\left(\frac{x}{p_k}\right) > 1.9\left\{(1+C)\frac{x}{p_1}-\frac{x}{p_k}\right\} \tag{17}$

を得る。 $10p_1 < p_k$ より

$\displaystyle 1.9\left\{(1+C)\frac{x}{p_1}-\frac{x}{p_k}\right\} > 1.9(0.9+C)\frac{x}{p_1} > 1.6\frac{(1+C)x}{p_1}$

なので( $1.6/1.9=0.84...$ )、(17)より

$\displaystyle \vartheta\left( (1+C)\frac{x}{p_1}\right) > 1.6(1+C)\frac{x}{p_1}$

となる。これはChebyshevの定理に矛盾する。 Q.E.D.

*1:思いましたが、なんかめちゃくちゃ難しいです。補題１を適用した $o(x/p)$ を使った議論は怪しいかもしれません(私が正確に理解できていないという意味)。

*2:正確にいうと、上に非有界な $\mathbb{R}$ 内の実数列 $x_1, x_2, \dots$ が存在して、 $\displaystyle \lim_{n \to \infty}\frac{\vartheta\left( (1+c)x_n\right)-\vartheta(x_n)}{x_n}=0$ が成り立つということ。以下、同様の言い回しを行う。

2018-08-29

8月13日に生まれた君へ

整数整数-813 整数-271

$8$ と $13$ は連続するFibonacci数だ。

これらを並べてできる $813$ という整数のことを考えてみよう。

素因数分解は $3\times 271$ だ。くっつけた $3271$ は素数。

$813$ は $7$ で挟むと素数になる。 $78137$

$7$ を $813$ で挟んでも素数だ。 $8137813$

素因数の $271$ は $e=\color{red}{2.71}82818284590...$ の最初の三桁に並んでいるが、 $813$ の $e$ 乗を計算してみると

$813^e=\color{red}{813}66615.0622303211885...$

の最初の三桁に $813$ が現れている。

$n$ と $2n$ の間に必ず素数があるというのがBertrandの仮説であった。

一方、 $n^2$ と $(n+1)^2$ の間に必ず素数があると言えるかは未解決の難問である(Legendre予想)。

実は、 $813$ と $2\times 813$ の間には素数が

$\begin{align}&821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, \\ &941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, \\ &1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, \\ &1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, \\ &1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, \\ &1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, \\ &1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, \\ &1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621\end{align}$

の $116$ 個あるが、 $813^2$ と $814^2$ の間にも素数が

$\begin{align}&660973, 660983, 661009, 661019, 661027, 661049, 661061, 661091, 661093, 661097, \\ &661099, 661103, 661109, 661117, 661121, 661139, 661183, 661187, 661189, 661201, \\ &661217, 661231, 661237, 661253, 661259, 661267, 661321, 661327, 661343, 661361, \\ &661373, 661393, 661417, 661421, 661439, 661459, 661477, 661481, 661483, 661513, \\ &661517, 661541, 661547, 661553, 661603, 661607, 661613, 661621, 661663, 661673, \\ &661679, 661697, 661721, 661741, 661769, 661777, 661823, 661849, 661873, 661877, \\ &661879, 661883, 661889, 661897, 661909, 661931, 661939, 661949, 661951, 661961, \\ &661987, 661993, 662003, 662021, 662029, 662047, 662059, 662063, 662083, 662107, \\ &662111, 662141, 662143, 662149, 662177, 662203, 662227, 662231, 662251, 662261, \\ &662267, 662281, 662287, 662309, 662323, 662327, 662339, 662351, 662353, 662357, \\ &662369, 662401, 662407, 662443, 662449, 662477, 662483, 662491, 662513, 662527, \\ &662531, 662537, 662539, 662551, 662567, 662591\end{align}$

の $116$ 個ある。

ちなみに、 $28^2$ と $29^2$ の間にある素数 $787, 797, 809, 811, 821, 823, 827, 829, 839$ の最小値と最大値の平均は

$\displaystyle \frac{787+839}{2}=813$

である。

2018-08-28

IMO 1990 Problem 3

高校数学整数整数-3

$\displaystyle \frac{2^n+1}{n^2}$ が整数となるような $1$ より大きい整数 $n$ を全て決定せよ。

解答 $n > 1$ とし、 $\displaystyle \frac{2^n+1}{n^2}$ が整数であると仮定する。 $n$ は奇数でなければならない。 $k:=\mathrm{ord}_3n$ とする。このとき、 $2^n\equiv -1 \pmod{3^{2k}}$ であるので、指数持ち上げ補題より( $x=4, y=1$ として適用)、 $k \geq 2k-1$ 、すなわち $k=0, 1$ が従う。よって、 $3$ で割れない奇数 $m$ を用いて $n=3^{\epsilon}m$ と書ける( $\epsilon \in \{0, 1\}$ )。 $n=3$ のときは $\frac{2^n+1}{n^2}=1$ である。 $m > 1$ と仮定して、 $m$ の最小の素因数を $p(> 3)$ とする。

$2^n\equiv -1 \pmod{p} \tag{1}$

である。 $i:=\mathrm{Ind}_2(p)$ とする(指数)。(1)より $i \mid 2n$ 。 $i$ が奇数であれば $i \mid n$ 、 $2^n \equiv 1 \pmod{p}$ となって(1)に矛盾。よって、 $i=2j$ と書ける( $j \geq 1$ )。 $j \mid n$ である。Fermatの小定理より $j \mid \frac{p-1}{2}$ なので、 $j < p$ 。 $p$ の最小性より $j=1$ or $3$ である。 $j=1$ とすると、 $i=2$ で $2^2 \equiv 1 \pmod{p}$ と矛盾である。 $j=3$ であっても $i=6$ で $2^6 \equiv 1 \pmod{p}$ となるので $p=7$ しかあり得ない。ところが、 $\mathrm{Ind}_2(7)=3 \neq 6$ なので矛盾。つまり、 $n=3$ のみである。