大きさの順でk番目の素数をpkとするとき，pk<2^2^kを示せ．

質問

大きさの順でk番目の素数をpkとするとき，pk<2^2^kを示せ．

回答No.3

yoikagari · ベストアンサー

チェビシェフの定理はいらないです。

p_(k+1)≦p_1*p_2*・・・*p_k +1を証明する。…※

※の証明
p_1*p_2*・・・*p_k +1=p_1*(p_2*・・・*p_k) +1だから
p_1*p_2*・・・*p_k +1はp_1で割り切れない。
p_1*p_2*・・・*p_k +1=p_2*(p_1*p_3*・・・*p_k) +1だから
p_1*p_2*・・・*p_k +1はp_1で割り切れない。
・・・・・・・・・・・・・・・・・・・・・・・
p_1*p_2*・・・*p_k +1=p_k*{p_1*p_2*・・・*p_(k-1)} +1だから
p_1*p_2*・・・*p_k +1はp_kで割り切れない。

したがって、p_1*p_2*・・・*p_k +1はp_1,p_2,・・・,p_kのいずれでも割り切れない。
p_1*p_2*・・・*p_k +1の素因数qをとると、qはp_1,p_2,・・・,p_kのいずれでもない
から、q≧p_(k+1)がいえる
よってp_(k+1)≦q≦p_1*p_2*・・・*p_k +1がいえる。
以上より※が証明された。

※の証明ここまで。

※を利用して数学的帰納法で示す。
k=1のとき
p_1=2，2^(2^k)=4だからk=1のときp_k＜2^(2^k)がいえる。

k＜nのとき
p_k＜2^(2^k)がいえると仮定する

k=nのとき
※の不等式
p_n≦p_1*・・・*p_(n-1) +1＜2^(2^1)*2^(2^2)*・・・+2^{2^(n-1)} +1
=2^{2+2^2 +・・・+2^(n-1)} +1＜2^{2+2^2 +・・・+2^(n-1)} +2^{2+2^2 +・・・+2^(n-1)}
=2^{1+2+2^2 +・・・+2^(n-1)}=2^(2^n -1)＜2^(2^n)
よってp_n<2^(2^n)がいえる。

以上より数学的帰納法により任意の正の整数kに対してp_k＜2^(2^k)であることが
証明された。

お礼

どうもありがとうございました！

回答No.2

Tacosan

Chebyshev の定理から pk ≦ 2^k < 2^(2^k).

回答No.1

hayato0320

示すのは無理ですが、感覚的には2^2^kはｋを上げていくとすごい傾きで増加していきますので、素数Pｋでは追いつけそうもないので、pk<2^2^kになりそうですよね。
まあ証明してないので絶対とは言えませんが。。。