7
高校数学解説
文献あり

4n+1型素数でベルトラン・チェビシェフの定理を考える

1294
1

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

まず, 今回のテーマであるベルトラン・チェビシェフの定理について紹介する.

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

任意の正整数nに対してn<p2nをみたす素数pが存在する.

これには次のような初等的な証明が知られている.

正整数nに対して2nCn4n2であり, 整数n4に対して4nn<2nCnである.

いずれも帰納法で容易に示される.

正の実数xに対し, P(x)x以下の素数の積とすると, P(x)<4x. ただし, 0<x<2のときP(x)=1とする.

0<x<2では明らか. したがって, 任意の整数n2に対してP(n)<4nを示せば十分. n=2のときは明らか. m2に対してP(2m1)P(m)=P(2m)P(m)2m1Cm=2mCm2の約数であるため, 補題2の1つ目の結果とあわせてP(2m1)P(m)=P(2m)P(m)4m1. この式を用いると帰納法で示すことができる.

正整数nに対して素数pp2n3のときvp(2nCn)logp2n. 特に, 2n<p2n3のときvp(2nCn)1.
また, 整数n3と素数p32n3<pnのときvp(2nCn)=0.

前者について, 実数xに対して2x2x1であるため,
vp(2nCn)=i=1logp2n2npi2npilogp2n
であるため示された.
後者について, 2n<p2より, vp(2nCn)=2np2np=22×1=0より示された.

以上の補題からベルトラン・チェビシェフの定理を示す.

(定理1 ベルトラン・チェビシェフの定理)

2,3,5,7,11,19,37,67,131が素数であるため, n<128のときについては示された.
ある整数n128について, n<p2nをみたす素数pが存在しないと仮定すると補題4より2nCnP(2n3)×(2n)2n3+2である. なお, ここで2n以下の素数が高々(2n3+2)個であることを用いた. 補題2,3を用いると, 22n3+1<(2n)2n3+3. x=2nとおくと, 2x23+1<x2x3+6. よって, log2<(2+18x)(logxx)であり, 右辺はx>eにおいて単調減少. ここで, n128よりx16(>e)であるが, (2+18x)(logxx)(2+1816)(log1616)<log2であるため矛盾. なお, xeにおいてlogxxが単調減少であることは微分法により容易に確かめられる.

4n+1型素数バージョンを作る

さて, ここからはベルトラン・チェビシェフの定理の考え方を応用する.

りぼーす氏がTwitterにて2023年5月3日に発表した 整数コンテスト の問5を考えよう.

4で割って1余る素数は無限に存在することが知られている. これらを小さい順にp1,p2,とおいたとき, 正の整数から実数への1変数関数Fを一つ決め, それが以下を満たすことを示せ.

任意の正の整数iに対してpi+1F(pi+1)

ただし, Fの表示として用いてよいのは, 実数の定数, 多項式, 指数, 対数, 階乗およびそれらの四則演算, 合成のみであり, 正の整数全体で定義されている必要がある.

0b<aをみたす整数a,bに対してaで割った余りがbの素数をan+b型素数と呼ぶ.

平方剰余の第一補充則より, 正整数mに対してm2+1の素因数は2または4n+1型素数である. よって, (2p1p2pi)2+1の素因数はpi+1以上であるため, 例えばF(n)=4(n!)2+1とすると問題の条件をみたす.
このようにして, 条件をみたすFの存在をいうのはさほど難しくないが, より小さく厳しいFを探してみよう.

補題3を利用すると, 2p1p2pi<P(pi)<4ipよりF(n)=16n+1が条件をみたすことがわかる. これでFは階乗を使わず表すことができた. さらに, m1,m2が互いに素な正整数のとき, m12+m22の素因数が2または4n+1型素数であるため, (P(pi+12))2+(P(pi)P(pi+12))2の素因数はpi+1以上である. ここで, 補題3の証明の途中で出てきた不等式P(2m1)P(m)4m1を用いると, F(n)=5×4n1が条件をみたすことがわかる.

4n+1型素数のみかければよいところで, すべての素数をかけているのはFを厳しい関数にする上でロスになっているため, その部分の評価を改善しよう. 正の実数xに対してP(a,b)(x)x以下のan+b型素数の積とする. ただし, x以下のan+b型素数が存在しないときはP(a,b)(x)=1とする. P(4,1)(x)を上手く上からおさえてより厳しい評価を得ることがひとまずの目標である.

補題3でP(n)の評価をするとき2n1Cnを用いたが, P(4,1)(n)の評価をするために新しく2n1Cnのかわりとなるnの関数を用意する.
正の実数xに対して(x)!(a,b)x以下のaで割った余りがbとなる正整数すべての積とする. ただし, x以下のaで割った余りがbとなる正整数が存在しないときは(x)!(a,b)=1とする.

正整数nに対して2n1(4n)!(4,1)n!で割り切れる.

v2(n!)=i=1log2nn2ii=1log2nn2in1
よってv2(2n1(4n)!(4,1))v2(n!).
pを奇素数, iを正整数とする. 4pinpi以下の正整数のうち4で割った余りが1piの倍数であるものはnpi個である. よって,
vp((4n)!(4,1))=i=1logp4n(4n 以下の正整数のうち 4 で割った余りが 1 で pi の倍数であるものの個数 )i=1logpnnpi=vp(n!)
ゆえに, 2n1(4n)!(4,1)n!で割り切れる.

正整数nに対して2n1(4n)!(4,1)n!23n3.

帰納法で容易に示される.

実数x2に対してP(4,1)(x)2x2.

任意の整数n2に対してP(4,1)(n)2n2を示せば十分. n=2,3,4のときは明らか. m2に対してP(4,1)(4m3)P(4,1)(m)2m1(4m)!(4,1)m!の約数であるため, 補題6とあわせてP(4,1)(4m3)P(4,1)(m)23m3. この式とP(4,1)(4m3)=P(4,1)(4m2)=P(4,1)(4m1)=P(4,1)(4m)を用いると帰納法で示すことができる.

さて, 補題7及びその証明で登場する不等式を利用してより小さいFをみつけよう. 12((P(4,1)(pi+34))2+(P(4,1)(pi)P(4,1)(pi+34))2)の素因数はpi+1以上である. したがって, F(n)=2n72+23n52が条件をみたすことがわかった.

ここまでの議論でFは指数関数でおさえられているが, ベルトラン・チェビシェフの定理の証明の流れをなぞると一次関数でおさえることができる. ベルトラン・チェビシェフの定理の証明における2nCnのかわりとなるnの関数を用意したい. 補題7で用いた2n1(4n)!(4,1)n!を利用すると実数x1においてP(4,3)(x)2x1を同様に示すことによって十分大きいiにおいてF(n)=52nが条件をみたすことがわかる. しかし, ここでは使う関数をもう少しだけ工夫してF(n)=32n+112が条件をみたすことを示してみよう.

任意の正整数nに対してn<p32n+112をみたす4n+1型素数pが存在する.

正整数nに対し,
cn=(3n2)!(4,1)(n)!(4,1)(n2)!(4,3)
とおく.

正整数nに対して奇素数pp3n10のときvp(cn)logp3n2.
特に, 4n+1型素数p3n2<p3n10のときvp(cn)1.
また, 4n+3型素数p3n2<pのときvp(cn)0.
さらに, 整数n174n+1型素数p3n10<pnのときvp(cn)0.

正整数m,aに対して, a1(mod4)のとき, m以下の正のaの倍数で4で割った余りが1のものはm+3a4a個, 4で割った余りが3のものはm+a4a個である. a3(mod4)のとき, m以下の正のaの倍数で4で割った余りが1のものはm+a4a個, 4で割った余りが3のものはm+3a4a個である.
正整数n, 正の奇数aに対してf(n,a)
f(n,a)={3n2+3a4an+3a4an2+a4a(a1(mod4))3n2+a4an+a4an2+3a4a(a3(mod4))
と定義する. このとき,
vp(cn)=i=1logp3n2f(n,pi)
が成り立つ.
実数x,yに対してx+yxy1であるため, 奇数aa1(mod4)のとき
f(n,a)3n2+3a4an+3a4an24a1
が成り立つ.
また, a3(mod4)のとき
3n24a=3n2+a4aまたはn2+3a4a=n2+4a4aが成り立つ. なぜなら, 3n24a<m13n2+a4an2+3a4a<m2n2+4a4aをみたす整数m1,m2が存在すると仮定すると2<3m2m1<3より矛盾するからである. ゆえに, 前者の場合は
f(n,a)=3n2+4a4an+a4an2+3a4a10
が成り立つ. 後者の場合は
f(n,a)=3n2+a4an+a4an24a10
よって, いずれの場合もf(n,a)0.
これらを利用することで補題9はいずれも容易に示される.

整数n2に対して1n2(274)n8<cn.

2n9については個別に調べて正しいことが確かめられる.
3n2(3n2+4)(3n2+8)<(3(n+8)2)!(4,1)(3n2)!(4,1)
1(n+4)(n+8)<(n)!(4,1)(n+8)!(4,1)
1n2+4<(n2)!(4,3)(n+82)!(4,3)
よって,
27n24(n+8)2<3n2(3n2+4)(3n2+8)(n+4)(n+8)(n2+4)<cn+8cn
より帰納法で示される.

(命題8)

5,13,17,29,37,61,97,149,229,337,509,709,1061,1597,2357,3529,5297,7933,11897,17789,26669
4n+1型素数であるため, n<2×20023<26667のときについては示された.
ある整数n2×20023について, n<p32n+112をみたす4n+1型素数pが存在しないと仮定すると補題9よりcnP(4,1)(3n10)×(3n2)n62である. なお, ここで3n2以下の奇素数が高々(n62)個であること及びv2(cn)=0を用いた. 補題7,10を用いて変形すると, 9×33n8<211n20×(3n2)n6. x=3n2とおくと, 9×3x24<211x230×x23x. よって, 15log322log2<40logxxであり, 右辺はx>eにおいて単調減少. ここで, n2×20023よりx200(>e)であるが,
40logxx40log200200<log3<15log322log2
であるため矛盾.

4n+3型素数についても, 2n1(4n)!(4,3)n!23n3を利用して実数x1に対してP(4,3)(x)2x1がわかり, cn=(3n2)!(4,3)(n)!(4,3)(n2)!(4,1)
とおいて同様に, 任意の正整数nに対してn<p32n+52をみたす4n+3型素数pが存在することが示せる.

参考文献

投稿日:2023820
更新日:202455
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

kkkaaa
25
9328

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. ベルトラン・チェビシェフの定理
  2. 4n+1型素数バージョンを作る
  3. 参考文献