第 7回講義5月26日資料

情報数学 Ⅰ 配布日時 2014 年 5 月 26 日
素数は無限個存在する。そこで自然数の剰余と素数の無限性について考える。
例えば、自然数 4 についての剰余を考えると、全ての自然数は余りが 0(割り切れる)、余りが 1,2,3
のいずれかである。
5, 13, …
素数についての剰余
3, 7, …
2
定理 2.7
4n  3 の形の素数は無限個存在する。
証明
2 以外の素数はすべて奇数である。それらは 4 で割ったときの余りは、1 か 3 であるので、
4n  1 か 4n  3 のどちらかの形である。
背理法で証明する。
4n  3 の形の素数は有限個と仮定する。
その中で、最大なものを q として、 4n  3 の形の全ての積を Q として、
M  4Q  1
と置く。つまり、 M  4 ( 3  7 11 q )  1。
M は M  4(Q 1)  3 と書けるので 4n  3 の形をしている。
M  q であり、 4n  3 の形の最大の素数を q としたので、 M は素数であるはずがなく合
成数である。
そこで、M の素因数分解を考えると、その素因数の中には少なくとも１つ 4n  3 の形の
素数がある。何故なら、 (4n 1) (4n' 1)  4 ( 4n n'  n  n' )  1 なので、 4n  1 の形をした
ものばかりならば、その積も 4n  1 の形であるが、 M は 4n  1 ではない。
従って、 M は 4n  3 の形の素数 3, 7, 11, …, q のいずれかで割り切れる。
つまり、 M  4 ( 3  7 11 q )   1 が 3, 7, 11, …, q のいずれかで割り切れる
ことになり、矛盾する。
ゆえに、 4n  3 の形の素数は無限個ある。
■
素数は無限個存在するので、
 1. 4n  1の形をした素数も、4n  3の形をした素数も無限個ある。　
4n  3の形をした素数は無限個ある。　 2. 4n  1の形をした素数は有限個で、
 3. 4n  1の形をした素数は無限個あり、
4n  3の形をした素数は有限個である。

のいずれかである。定理 2.7 より、1. か 2. が成立することになる。
実は、この講義で証明を行う予定であるが、 4n  1 の形をした素数(簡単にこれから 4n  1 型素数
などと呼ぶ)も無限個存在する。しかし、その証明は 4n  3 型素数の時よりも難しい。この点を十
分に理解してほしい。
情報数学 Ⅰ 配布日時 2014 年 5 月 26 日
以下の補題をまず証明する。ただし、主張だけを理解してもらい、定理 2.10 へスキップする
かもしれない。
補題 2.8
x 2  1 の形の数の素因数は 2 か 4n  1 の形である。
証明
なぜならば、2 以外の素因数 p を持てば、
x 2  1  0 mod p
より、
x 2   1 mod p
なので、 x  1 mod p となる。
4
p  2 だから、 x 2 も x も  1 mod p にはならない。
よって、ord[ p ]( x ) = 4 となり、 4 | p 1 。
従って、 4n  p 1 、つまり、 p  4n 1 とおける。■
【位数について】
自然数 m と、 m と互いに素な整数 a に対し
a k  1 mod m
となる最小の自然数 k を ord[ m ]( a ) と書き、 a の m を法とする位数という。
法が明らかな時は、単に ord( a ) とも書く。
補題 2.9
m と互いに素な a に対し、
a d  1 mod m
ならば、ord( a )｜ d となる。
証明
ord( a )  t とおく。
d t q  r
(ただし、 0  r  t )
唯一に表される。
a tq  r  (a t ) q a r  a r
だから、 a  1 。
r
しかし、 0  r  t と t の最小性から、 r  0 。 █
【オイラーの関数（オイラーのトーシェント関数・・・後述）  (n) との関係】
上述の定理より、特に
ord( a )｜  (m)
が成り立つ。 m が素数 p でその法の場合は、
ord( a )｜  ( p)
が成り立つ。
→
ord( a )｜ p  1
情報数学 Ⅰ 配布日時 2014 年 5 月 26 日
定理 2.10
4n  1 型素数は無限個存在する。
証明
背理法で証明する。
4n 1 型素数は有限個と仮定する。
小さい方から、5,13,17,…, p と並べる。つまり、 4n 1 型素数の最大の素数は p である。
M  (2  5 13 p) 2  1 と置くと、 M は 4n 1 の形をしている。
M が素数とすると、 p が最大である事と矛盾するので、 M は合成数である。
その最大の素因数 q とすると、 M は x  1 の形である事から、補題 2.8 より、その素因数は
2
2 または 4n  1 の形、つまり、 q は 4n  1 の形だから、
5,13,17,…, p
のどれかと一致する。しかし、それで割れば 1 余るはずなのに割り切れてしまうから矛盾。█
以上に関連して、 6n  5 型素数なども主張も考えられるが、何らかのかたちでこの講義にももう
一度登場するであろう。
以上を一般化した次の定理が知られている。
定理 2.11 (ディリクレ)
自然数 a, b が互いに素とする。このとき an  b の形の素数は無限に存在する。
証明
証明は大変なので、この講義では省略する。
■
注意)仮定「 a, b が互いに素」が無いと定理は成り立たない。実際、(a, b )  d  1 だとすると、
a  a' d , b  b' d の形に書けるので、
an  b  d ( a' n  b' )
となり、 n  0, b'  1 (したがって b  d )の場合を除いて、 an  b は合成数になる。
情報数学 Ⅰ 配布日時 2014 年 5 月 26 日
３．素数の分布について
いままでの素数は無限個あることから「いくらでも大きい素数がある」ことはわかったが，も
う少しくわしく、どれくらいの頻度で素数が散らばっているのかを考えると、いままでのことか
らは何のヒントも得られない。
素数の頻度に関する有名な定理である『素数定理』についても述べる。
－素数定理歴史 Wiki －
この定理は、18 世紀末にガウスやルジャンドルによって予想された（ガウス自身の言によればそれ
は 1792 年のガウス 15 歳のときである）
。実際にはルジャンドルが初めて自身の著『数の理論』で公表
し、少年ガウスがそれを知っていたことはガウスの死後の 1863 年に全集が出るまでは知られず、ガウ
ス自身は素数定理については友人エンケに一度だけ手紙（1849 年）で触れただけであった。
その後チェビシェフによる部分的な結果（1850 年頃）や、リーマンによる新たな解析的方法が発表さ
れたが、最終的には 1896 年にド・ラ・ヴァレー・プーサンとジャック・アダマールがそれぞれ独立に
証明した。当初与えられた証明はゼータ関数と複素関数論を用いる高度なものであったが、1949 年に
アトル・セルバーグとポール・エルデシュは独立に初等的な証明を与えた。ウィーナーや池原止戈夫ら
によるタウバー型定理によって、素数定理と「ゼータ関数が Re s = 1 上に零点を持たないこと」との
同値性がすでに確立されていたために、この初等的な証明は大きな驚きをもって迎えられた。
－歴史終了
3.1 素数計数関数
自然数 n までの素数の個数関数  ( n ) とする。
定義 3.1 自然数 n に対して、  ( n )  n 以下の素数の個数
 ( n ) は素数計数関数(Prime Counting Function) と呼ばれる。
なお、変数としては実変数 x でもって同様に  ( x ) が定義される。
例
 (1 )  0 ,  ( 2 )  1 ,  ( 3 )  2 ,  ( 4 )  2 ,  ( 5 )  3 ,  ( 6 )  3 ,  ( 7 )  4
 (10)  4 ,  (100)  25 ,  (1000)  168 ,  (10000)  1229 ,  (100000)  9592 ,
 (106 )  78798 ,  (107 )  664579 , …,  (10 24 ) 
 (10 25 )
2013 年に
18,435,599,767,349,200,867,866
が計算された。
定理 3.2(素数定理)
n
log n
 ( n ) ～　つまり、
lim
n
 (n)
n
l o gn
 1。

Download Report