数学A 整数問題 問題 35 解説

方針・初手

素数の列 $p_1,p_2,\dots$ は小さい順に並んでいるので、$p_1,\dots,p_n$ 以外の素数はすべて $p_{n+1}$ 以上である。

したがって、積

$$ P=p_1p_2\cdots p_n $$

をおき、$P+1$ の素因数を考えるのが自然である。これはユークリッドの素数無限性の証明と同じ発想である。

解法1

まず

$$ P=p_1p_2\cdots p_n $$

とおく。

(1)

任意の $i=1,2,\dots,n$ に対して、$P$ は $p_i$ で割り切れる。したがって

$$ P\equiv 0 \pmod{p_i} $$

である。

よって

$$ P+1\equiv 1 \pmod{p_i} $$

となる。したがって、$P+1$ は $p_i$ では割り切れない。

これはすべての $i=1,2,\dots,n$ について成り立つので、

$$ p_1p_2\cdots p_n+1 $$

は $p_1,p_2,\dots,p_n$ のいずれでも割り切れない。

(2)

$P+1>1$ であるから、$P+1$ は少なくとも1つの素因数をもつ。その素因数の1つを $q$ とする。

すると

$$ q\mid P+1 $$

である。

(1)より、$P+1$ は $p_1,p_2,\dots,p_n$ のいずれでも割り切れない。したがって、$q$ は $p_1,p_2,\dots,p_n$ のどれとも一致しない。

素数は小さい順に

$$ p_1,p_2,\dots,p_n,p_{n+1},\dots $$

と並んでいるので、$p_1,\dots,p_n$ に含まれない素数 $q$ は

$$ q\geqq p_{n+1} $$

を満たす。

一方、$q$ は $P+1$ の素因数であるから

$$ q\leqq P+1 $$

である。よって

$$ p_{n+1}\leqq q\leqq P+1 $$

となり、

$$ p_{n+1}\leqq p_1p_2\cdots p_n+1 $$

が成り立つ。

(3)

$k=1,2,\dots,n$ に対して

$$ \log_2 p_k<2^k $$

が成り立つと仮定する。

(2)より

$$ p_{n+1}\leqq p_1p_2\cdots p_n+1 $$

である。両辺の $\log_2$ を考えるため、まず積の大きさを評価する。

仮定より

$$ \log_2 p_1+\log_2 p_2+\cdots+\log_2 p_n < 2^1+2^2+\cdots+2^n $$

である。左辺は積の対数だから

$$ \log_2(p_1p_2\cdots p_n) < 2^1+2^2+\cdots+2^n $$

となる。

等比数列の和より

$$ 2^1+2^2+\cdots+2^n=2^{n+1}-2 $$

であるから、

$$ \log_2 P<2^{n+1}-2 $$

である。したがって

$$ P<2^{2^{n+1}-2} $$

となる。

ここで $n$ は自然数なので $2^{n+1}\geqq 4$ である。よって

$$ P+1<2^{2^{n+1}-2}+1<2^{2^{n+1}} $$

が成り立つ。

(2)の不等式と合わせると

$$ p_{n+1}\leqq P+1<2^{2^{n+1}} $$

である。したがって、底 $2$ の対数をとって

$$ \log_2 p_{n+1}<2^{n+1} $$

を得る。

解説

この問題の中心は、$p_1p_2\cdots p_n+1$ を考える点である。この数は $p_1,\dots,p_n$ のどれで割っても余りが $1$ になるため、それらの素数を素因数にもたない。

したがって、その素因数は必ず $p_{n+1}$ 以上であり、これが

$$ p_{n+1}\leqq p_1p_2\cdots p_n+1 $$

につながる。

(3)では、対数をとることで積を和に変えるのが要点である。仮定

$$ \log_2 p_k<2^k $$

を足し合わせると、積 $p_1p_2\cdots p_n$ の大きさを上から評価できる。

答え

(1)

$$ p_1p_2\cdots p_n+1 $$

は $p_1,p_2,\dots,p_n$ のいずれでも割り切れない。

(2)

$$ p_{n+1}\leqq p_1p_2\cdots p_n+1 $$

が成り立つ。

(3)

$k=1,2,\dots,n$ に対して $\log_2 p_k<2^k$ が成り立つならば、

$$ \log_2 p_{n+1}<2^{n+1} $$

も成り立つ。