1. No category

情報数学 Ⅰ 配布日時 2014 年 6 月 2 日
素数を小さいものから順番に p1  2, p2  3, p3  5, p4  7, 
と置くと次の非常に粗いが関係式が
成り立つ。
系 3.3
pn  2 2
n
証明
今まで素数に関することより、
pn1  p1 p2  pn  1
が成立する。
以下、帰納法で証明する。
p1  2  4  2 2 であるから、 n  1 では正しい。
1
n  1 とし、 1  k  n に対して、 p k  2 2 とするとき、
k
pn1  p1 p2  pn  1  2 2
1
 22
 22    2n
n 1
1
 22
 1  22
n 1
1
 22
n 1
n 1
2
1
。
■
素数計数関数  ( x ) の評価に関しては次のことが言える。
系 3.4
 ( x )  log10 log10 ( x)
(x  2 )
証明
2  x  3 に対して、  ( x ) 1  log10 log10 (3)  log10 log10 ( x) である。
x  3 に対しては、 n   ( x ) と置けば、 pn  x  pn1 、 p  2 である。
系 3.3 より、 p n 1  2
2 n 1
であるので、 x  2 2
n 1
となり、対数を取れば、
l o 10g x  2 n1 l o 10g2 となり、もう一度対数を取れば、
log10 log10 x  (n  1) log10 2  log10 log10 2
情報数学 Ⅰ 配布日時 2014 年 6 月 2 日
 n  ( log10 2  1) n  log10 2  log10 log10 2
 n  ( log10 2  1) 2  log10 2  log10 log10 2
 n  3 log10 2  log10 log10 2  2  n   ( x)
■
[対数積分]
対数積分 li( x ) とは、 x  1 なる正の実数で与えられる関数である。
li( x ) =
関数

x
0
dt
log e t


x
0
dt
ln( t )
1
は t  1 において特異点であるが、x  1 においてその特異点の積分はコーシーの主
log e t
値として考える。
つまり、 x  1 に対して、

1


li( x ) = lim 
  0
0
dt

ln(t )
x
dt 
  ln(t ) 
1
となる。
他によく使われる関数として、補正対数積分関数 Li( x ) = li( x ) － li(2) で定義される関数がある。
ここで、li(2) = 1.0451637801174927848445888891946131365226155781512…
x   では、  (x) ~ li( x ) ~ Li( x ) が成り立つ。
以下は素数計数関数に関する表です。
情報数学 Ⅰ 配布日時 2014 年 6 月 2 日
【素数砂漠】
素数を小さい方から並べて p1  2, p2  3, p3  5, p4  7,  と書いている。
pn  pn1  pn とおく(つまり、 p n は素数列 p n の階差数列)と、隣接する二つの自然数の
うち一方は偶数だから、 pn 1  n  1 、つまり、隣接する素数は 2 と 3 だけである。
特に、 p n が 2 となる二つの素数 p n と p n 1 は双子素数であるという（あとでこの講義で双
子素数の話が出る）。3 と 5 や 11 と 13 は、各々双子素数である。双子素数が無限にあるかは
未解決の難問である。
pn  N 1 となる時には、 pn  1, pn  2,, pn1  1 は全て合成数になり、これら N 個の続
いた自然数には素数はひとつもない。このような合成数の続いた列を長さ N の素数砂漠と呼ぶ
ことにする。
情報数学 Ⅰ 配布日時 2014 年 6 月 2 日
以下に１００までの素数を箱枠で示している。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
100 までの間では、90～96 までが最長７の素数砂漠である。
定理 3.5
任意の自然数 N に対し、長さが N 以上の素数砂漠が存在する。
証明
( N  1) !  k
( k  2, 3, 4,, N  1)
という N 個の続いた自然数は、各々 k という 1 でも自分自身でもない約数をもつので全て合
成数である。よって、少なくとも長さ N の素数砂漠になっている。■
丁度長さ N の素数砂漠や、長さが丁度 N である素数砂漠を与える最小の先頭の数を求めるのは
難しい。素数間隔は規則が予想つかず、ランダムに見える。現在でも未解決な問題が多い分野の
ひとつである。
[素数の逆数の和]
素数は無限個あるが、その頻度・分布に関してもう少し詳しいことが分からないか？と言
う疑問がある。
次の結果は最初にレオンハルト・オイラーによりゼータ関数を研究することでもたらされた。
以下で述べる証明はエルデシュによるもので、より直接で、また簡潔なものとなっている。素数
が無限個存在することは証明に用いないため、そのことの別証明にもなっている。
定理 3.6
素数を小さい方から順に、 p1 , p 2 , p3 , … とすると、

1
p
i 1
である。
i

情報数学 Ⅰ 配布日時 2014 年 6 月 2 日
証明
背理法を使って証明する。

1
p
i 1
  とする。 すると、ある自然数 k が存在し、
i


i k 1
となる。
1
1

pi
2
ここで、 Q  p1 p2 p3  pk として、自然数 n  1, 2, 3,  に対して、
1 n Q と言う数を考えると、これらは p1 , p2 , p3 ,  , pk で割れません。
従って、 1 n Q のすべての素因子は、素数 pk 1 , pk  2 , pk 3 ,  にあるはずなので
  
1
1
   

n 1 1  n Q
s 1  i  k  1 pi

s
s


1
      1 .

s 1  2 

右辺の和は、その項の中に左辺の全ての項を含んでいる。

つまり、
1
1  nQ
は収束する。
n 1

他方、

1
1
1  1




   となりますので、これは矛盾です。■
2Q n1 n
n 1 1  n Q
n 1 2n Q
n
普通、
1
p
i 1
~ log(log n)
と言われています。
i
これで「いくらでも大きい素数がある」ことはわかったが，もう少しくわしく、どれくらいの頻度で
素数が散らばっているのかを考えると、この証明からは何のヒントも得られない。
素数の頻度に関する２つ目の定理をあげる。
それはベルトランが素数表を挑めて予想し，後にチェビシェフが証明した定理です。
チェビシェフの証明はガンマ関数を使ったものでして、この定理の証明は非常に難しいとも言われま
した。しかし現在では後に「放浪の数学者」といわれたハンガリー生れの鬼才エルデシュが高校生の
ときに発見した初等的な証明があります(高校レベル)。以下の証明はエルデシュの原論文の通りでなく，
少し改変されています。
チェビシェフの定理．任意の実数 x  1 に対して、
x  p  2x
を満たす素数 p が存在する。
普通は、チェビシェフの定理は
「2 以上の自然数 n に対し、 n  p  2n を満たす素数 p が必ず存在する。
」
と述べられることが多い。
情報数学 Ⅰ 配布日時 2014 年 6 月 2 日
n  2,
n  3,
n  4,
例
2  p 4
3  p 6
4  p 8
他の有名な未解決問題
平方数間に素数はあるか。つまり、全ての自然数 n に対して、 n 2 と (n  1) の間に素数は存
2
在するか。
12  1 ,
2 2  4 , 32  9 , 4 2  16 , 5 2  25 , 6 2  36 , 7 2  49 , 8 2  64 ,
9 2  81 ,…
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127
素数計数関数  (x)
平方数間に素数はあるか。  n N ,
 ((n  1) 2 )   (n 2 )  1
チェビシェフの定理  n N ,  (2n)   (n)  1
以下、チェビシェフの定理の証明を行って行く。
定理 3.7
チェビシェフの定理( ベルトラン・チェビシェフの定理)
自然数 n と 2n の間に素数がある。
補題 3.8
cn 
n 1 に対して、
2n
Cn  2 2 n1
証明（数学的帰納法）
c1  2  21 , c2  6  23 であるので、 n 1, 2 では正しい。
n のとき正しいとすると
cn1  cn
であり、
(2n  1)(2n  2)
2(2n  1)
 cn
2
n 1
(n  1)
2n  1
 2 であるから、
n 1
cn1  2 2n1  2 2  2 2n1  2 2( n1) 1
となり、 n  1 のときも正しい。 ■
情報数学 Ⅰ 配布日時 2014 年 6 月 2 日
系 3.9
2 n 1
証明
Cn 
1
cn  2 2( n1)
2
明らか。
■
系 3.10
( n  1) 以上 ( 2n  1) 以下の素数の積は、 2 2 n2 より小さい。
このとき該当する素数がなければ積を l と解釈する。
証明
2 n 1
Cn 
(n  1) (n  2)(2n  1)
を素因数分解すると、
1  2(n  1)
( n  1) 以上 ( 2n  1) 以下の素数は分子に１回現れるだけで、約分されないから
( n  1) 以上 ( 2n  1) 以下の素数の積

2 n 1
Cn
となるので、系１を適応する。■
補題 3.11
n までの素数の積 Pn は
1
2 2 n1   4 n
2
証明（数学的帰納法）
以下である。
P2  2 23 , P3  6  25 , P5  30  2 9 など，小さい n については正しい。
n より小さい場合は正しいとして数学的帰納法により n のときを示す。
偶数 2m は素数でないから P2 m  P2 m1 であり， n を奇数 2m 1 としてよい。
帰納法の仮定から
Pm  2 2 m1
( 2m  2m  1 )
である。他方 ( m  1) から ( 2m  1) までの素数の積は，上述の系 2 により 2 2 m2 より小さいから
n  2m 1 として
Pn  P2m1  2 2m1  2 2 m2  2 2n1
である。
■
補題 3.12
n  4 のとき
cn 
2n
Cn 
4n
n
情報数学 Ⅰ 配布日時 2014 年 6 月 2 日
44
 64 であるので成立している。
4
n  4 の n について正しいとして、 n＋1 のときにも成り立つことを示す。
c4  70 
証明（数学的帰納法）
(n  1) cn1  2(2n  1) cn
(n  1) cn1  2(2n  1)
であり、
4n
n
2n  1
 2 なので、上の右辺は、 2 2 4 n  4 n1 より大きい。■
n
補題 3.13
n ! を素因数分解したとき，ある素数 p が p r の形で含まれたとすると
n
n  n 
r      2    s   
 p  p 
p 
である。ここで、 

は切り捨て関数(ガウス関数)を表している。
上式の右辺は、有限和である。
証明
n
 
n
p
1 から n までの p の倍数は   個である。 n ! を p   で割ると、全体として p の倍数は
 p
 n 
2
除かれるが、 p の倍数は残り、 p の累乗指数が１つ減る。その個数は  2  個である。
p 
3
それを除くと p の倍数が、累乗指数が２つ減って残る。この操作を繰り返すと、
補題の式となる。■
系 3.14
cn 
2n
Cn を素因数分解すると， 2n より大きい素数は現れても p 1 の形である。
それ以下の素数が p の形で現れれば， p  2n である。
k
k
証明
2n  n 
n
 s   2  s  （*)は 0 か 1 である。実際, s の小数部分が 0.5 未満ならば 0, 0.5 以上ならば 1
p
p  p 
である。
さて,
2n  p なら cn に現れる上式の値は s 1 のときだけで， p 0 か p 1 である。
2n 以下の p については， p r  2n  p r 1 である r (  2 )が存在し，
（*) は s 1, 2,, r について
現れる。
各々の s に対して（*）は 0 か 1 なので，p
k
k
r
の形で現れるとき k  r であり, p  p  2n である。
■