第12回講義6月30日資料

情報数学 Ⅰ 配布日時 2014 年 6 月 30 日
今後の予定
１３回７月７日、１４回７月１４日
１５回７月２１日講義＆模擬試験
定期試験７月２８日(月) 10:55~12:05 教室 20831
自筆ノートのみ持ち込み可、講義のプリント等の印刷物は持ち込み不可
演習の解答例
（１）41 より小さくて，41 と互いに素な自然数の個数  (41)
41 は素数なので、
1,2,3,…, 40 と 41 は互いに素である。
従って、  (41)  40 である。
（２） 81 3 より小さくて，81 と互いに素な自然数の個数  (81)
4
81 34 と互いに素な 81 以下の自然数は、
1,2,
4,5, 7,8, 10,11,
…
∴  (81)  2  27  54
79,80 である。
（３） 48  2 3 より小さくて，48 と互いに素な自然数の個数  (48)
4
次のページに解答例あり。
オイラー関数の性質
 (n)  #{ x  N | 1 x  n, ( x, n)  1}
・素数 p については、  ( p)  p 1 である。
・素数ベキ
p k については、1 から p k までで p で割り切れる数は p k 1 個あるので、
 ( p k )  p k  p k 1 である。
・自然数 n, m が互いに素、すなわち (n, m)  1 であれば、
 (n m)   (n)  (m)
が成立する。
【直観的な説明】碁石を n m 個長方形に並べ、1 から順に番号をつけるとわかりやすい。つ
まり、n 行 m 列の長方形に番号付きの碁石を並べる。そのなかから、まず n と互いに素
でない 1 以外の碁石を除く。そうすると n の約数が属する行がなくなる。次に m と互い
に素でない 1 以外の碁石をとり除く。m の約数（1 以外）が属する列の碁石がなくなる。
残った碁石の数が  (n m) である。数えるには、上下左右に形をくずさないで縮めると
 (n) 行  (m) 列の長方形になることがわかる。
情報数学 Ⅰ 配布日時 2014 年 6 月 30 日
従って、自然数 n を n  p1 1 p2 2  pl
e
e
el
と因数分解すると、
 (n)   ( p1e p2 e  pl e )   ( p1e )   ( pl e )
1

2
e 1
 p1 1  p1 1
e
l
1
  p
el
l
 pl
l
el 1


1 
1
1  
1 
e
e
e 
 p1 1 p2 2  pl l 1   1    n 1   1  
p1  
pl 
p1  
pl 


定理 4.7
オイラー関数  (n) は以下の性質をもつ。
(1)  (1)  1
(2) 素数 p については、  ( p)  p 1
(3) 素数ベキ p については、  ( p k )  p k  p k 1  p k 1 ( p  1)
(4) 自然数 n, m が互いに素であれば、  (n m)   (n)  (m)
k
(5) n  p1 1 p2 2  pl
e
e
el
と因数分解されると、

1 

1 
1
 1  
 (n)  n 1   1 
p1  
p2  
pl 

証明
今までの説明より、省略する。
先週の演習の（３）の計算
 1 
 (48)   (2 4 3 )  48 1   1 
 2 
例題８.
1
1 2
  48   16
3
2 3
n  2 のときは、  (n) は偶数である。

e 1
解答例  (n)  p1 1  p1 1
e
  p
el
l
 pl
el  1

を考える。
n が奇数の素因子 p1 を持ったとすると、
p
1
e1
e 1
 p1 1
は奇数から奇数を引くので偶数である。
偶数の素因子は 2 だけなので、
2 k  2 k 1  2 k 1
偶数となる。
例題 9.
解答例
█
 (2n)   (n) であるための必要十分条件は、 n が奇数であることを証明せよ。
情報数学 Ⅰ 配布日時 2014 年 6 月 30 日

「 n が奇数ならば、  (2n) 
 (n)
である。」
n が奇数ならば、 (n, 2)  1 なので、
 (2n)   (2)  (n)  1  (n)   (n) 。

対偶「 n が偶数ならば、  (2n) 
n
 (n)
」で証明する。
は偶数なので、 n  2  n ' と書ける。ここで、 k  1 、 n ' は奇数である。
k
 (2n)   (2 k 1  n ' )   (2 k 1 )  (n ' )  2 k  (n ' )
他方、  (n)   (2  n ' )   (2 )  (n ' )  2
k
k
となり、  (2n) 
例題１０.
解答例
 (n)
k 1
 (n ' )
が証明された。 █
 (n)  2 となるとき、 n はどのような数か。
n  p1 1 p2 2  pl l と素因数分解すると、
e
e
e

1 
1 

1
  p1e 1  p1 1  pl e 1  pl  1  2
  1 
 (n)  n 1   1 
p1  
p2  
pl 

1
l
５以上の素因子を含めば、  (n)  4 となるので、 n は 5 未満の素因子である 2 か 3
の可能性しかない。
つまり、 a, b を自然数として n  2 , 3 , 2 3 となる。
a
b
a
b
 (2a )  2a 1  2 の場合 a  2 となり、 n  4 。
 (3a )  3a 1  2  2 の場合 a 1 となり、 n  3 。
 (2a 3b )  2a 1 3b1 2  2 となるので、 a  b 1 となり、 n  6 。
以上より、 n  3, 4, 6
となる。
■
情報数学 Ⅰ 配布日時 2014 年 6 月 30 日
５．メルセンヌ素数、完全数、フェルマー素数
素数は無限にあるので最大の素数は存在しませんが、人類が知っている限りでの最大の素数と
いうのは存在します。
定義 5.1
m  N に対し、 M m  2 m  1 をメルセンヌ数といい、
特に、 M m が素数のときメルセンヌ素数という。■
現在までに(2014 年 6 月末)、メルセンヌ素数は 48 個知られている。
発見されている最大のメルセンヌ素数(最大の素数)は
2578851611
(GIMPS, Jan. 2013)である.
メルセンヌ数を 2 進数で表すと、 n 桁の 1111 である。
歴史的には、1644 年にメルセンヌが、 2  1 が素数になるのは、 n  257 では、 n = 2, 3, 5, 7,
n
13, 17, 19, 31, 67, 127, 257 だけであると主張した。しかしその主張の一部は誤っていた。
リストに含まれていない M 61 , M 89 , M 107 が素数であり、リストに含まれている M 67 ,
M 257 は合成数であった。
再度書きますが、 M 67 が素数でないことは、1903 年 10 月、フランク・ネルソン・コールによ
り示された。彼はニューヨークで開かれたアメリカ数学会で 193707721 × 761838257287 を黒
板に計算し、 M 67 と一致することを証明した。この間一言もしゃべらず、席に戻った後、少し間
を置いて拍手が沸き起こったと伝えられている。
命題 5.2
n を自然数とする。
（1）2  1 という形の数（メルセンヌ数）が素数になるのは， n が素数の場合に限ることを示
せ。
n
（2） 2  1 という形の数が素数になるのは, n が 3 以上の奇数では割り切れない場合に限る
ことを示せ。
証明
n
（1） n が合成数で，
n  k s,
1 k  n
の形に書けるなら，
2n  1  (2k ) s  1  (2k  1) ( 2k ( s1)  2k ( s2)    2k  1)
の形に因数分解できる．したがって 2  1 も合成数である．
n
（2） n が 1 より大きい奇数 s で割り切れて，
n  k s,
1 k  n
の形に書けるなら，
2n  1  (2k ) s  1  (2k  1) ( 2k ( s1)  2k ( s2)    2k  1)
情報数学 Ⅰ 配布日時 2014 年 6 月 30 日
と因数分解できる．したがって 2  1 は合成数である．■
n
n  7 なら s  7, k 1 に対して上の式が成りたつ．したがって 2 7  1 は
上の(2)の例：
21  1  3 で割りきれる．実際，128＋1＝129＝3×43 。
メルセンヌ素数
人類が知りえる最大の素数は、現時点では、最大のメルセンヌ素数 M n  2  1 である。
n
命題 5.2 より、 p  2  1 の形の素数であるためのには、 n が素数である必要がある。
n
しかしながら、 p が素数でも M p は素数とは限らない。
M 2  2 2  1  3 , M 3  23  1  7 , M 5  25  1  31 , M 7  27  1  127
M 11  211  1  2047  2389 メルセンヌ素数でない
現在知られているメルセンヌ素数 M p は 48 個である。以下では p を列挙する。
p  2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689,
9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433,
1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 25964951
― メルセンヌ素数発見の歴史－
紀元前 5 世紀 p  2, 3
古代ギリシャの数学者
紀元前 3 世紀 p  5, 7
古代ギリシャの数学者
1456 年
不明
p  13
1588 年
ピエトロ・カタルディ
p  17,19
1772 年
レオンハルト・オイラー
p  31
1876 年
エドゥアール・リュカ
p  127
1883 年
イヴァン・パヴシン
p  61
1911 年
R・E・パワーズ
p  89
1914 年
R・E・パワーズ
p  107
p  521
1952 年
ラファエル・M・ロビンソン*計算機利用
・・・
p  1398269
1996 年
GIMPS これ以降
【未解決問題】
・メルセンヌ素数は無限に存在するか？
・素数 p に対して M p が合成数であるとき、これをメルセンヌ合成数と呼ぶことにして、
それは無限に存在するか？
・平方因子を持つメルセンヌ数 M p ( p は素数）が存在するか？
・ n を奇数とするとき、次の 3 つの条件のうち 2 つが満足されれば、残りの 1 つも満足され
ると予想されており、 n  100000 に対してこの予想は正しいと確認されている。
1.
M n が素数
情報数学 Ⅰ 配布日時 2014 年 6 月 30 日
4k  3
2. n  2k  1 または
3. (2n  1) 3
が素数
完全数
この節では、ピタゴラスにより重要性が唱えられた完全数に関して述べる。
以前、自然数 n と整数 m に対して、一般化した約数関数  m (n) 

m
d を記した。
d |n
そして、  (n)   1 (n) であり、 d (n)   0 (n) となっていて、約数の個数関数、約数関数を含ん
でいること、さらに、この関数  m (n) は乗法的関数となっていることを言及した。
特に、  m (n) で m  1 の場合は、  1 (n) 

d |n
1
となる。
d
a
自然数 n が素数ベキである場合、つまり素数 p のとき、
 1 ( p a )  
d|p
a
1

pd
a
p
1
p a 1
1
1
p
1
i

i 0
ここで、  1 ( p )  lim  1 ( p ) 

a
a 
1
pa
p 1
p

p
と置くと、次の補題が言える。
p 1
補題 5.3
奇素数 p, q に対して、
(1) 自然数 a , b が、 1  a  b   ならば
1   1 ( p a )   1 ( p b )
(2) 自然数 a , b が 1  a , b   かつ p  q ならば
 1 (q b )   1 ( p a )
が成立する。
証明 (1) 奇素数 p と 1  a  b   なる自然数 a , b に対して、
1   1 ( p a ) 
a
 p i  1 
i 0
a
1
1
   a   1 ( p b )   p i 
p
p
i 0
b
p
i  a 1
i
情報数学 Ⅰ 配布日時 2014 年 6 月 30 日
より、明らか。
(2) 1  a , b   , p  q に対して、
 1 (q a )   1 (q  ) なので、  1 (q  )  1 ( p) を示せば良い。
p  q で、しかも p, q は奇素数なので p, q の差は 2 以上なので、
p 1  q が成り立つ。
p 1  q


p  q 1
 1
q 1
p
 q  q 1 
q
1
 1
q 1
p
故に、  1 (q )   1 ( p) が成り立つ。

補題 5.4
q 1
p
█
自然数 x 1, y 1 である自然数に対して、
x y 
y
x

y1
x 1
これは、上の補題 5.3 で a  b   、 p  q ならば
 1 (q  )   1 ( p  )
に該当する。
証明
x y 

定義 5.5
例
y  x

y
x

y1
x 1
xy  y  xy  x

y ( x  1)  x ( y 1)
■
n  N に対し, n の約数の和を  ( n ) と表す.
 ( n )  2 n をみたすとき, n を完全数(perfect number) という。
 ( 6 )  1 2  3  6  2  6 ,  ( 28 )  1 2  4  7 14  28  2  28
そのほかに、496, 33550336, 8589869056 などがある。
【偶数の完全数】
偶数の完全数については、よく知られている。
情報数学 Ⅰ 配布日時 2014 年 6 月 30 日
補題 5.6( ユークリッド原論第 IX 巻の最後の命題)
m  N に対し、 q  2 m 1 が素数ならば、
n  2 m1 q  2 m1 ( 2 m  1 ) は完全数である.
q  2 m 1 が素数なら、奇素数であるので 2 の素因子を持たない。
証明
q  2 m1 ( 2 m  1 ) の約数は、
1, 2, 2 2 ,  , 2 m1 ,
従って、 n  2
m1
q, 2q, 2 2 q , , 2 m1 q
であるので、総和は
 (n)  (1 2  2 m1 ) ( 1 q)  (2 m  1) (1 q)  2 m (2 m 1)  2  2 m1 (2 m 1)  2 n
となるので、 n は完全数である。
■
補題 5.7
自然数 m に対して、もし n  2
m1
( 2 m  1 ) が完全数であれば、 2 m 1 は素数である。
証明背理法で証明をする。つまり、 2 m 1 は素数でないとする。
a  2 m 1 と置き、 a の約数を d1 ,, d r とする。 a は 2 を素因子として含まないので、
n  2 m1 ( 2 m  1 ) の約数は
d1 , 2 d1 , , 2 m1 d1 ,
d 2 , 2 d 2 , , 2 m1 d 2 ,
,
dr , 2 dr ,
, 2 m1 d r
となり、 a の約数の総和は  (a )  d1  d 2    d r なので、
 (n)   ( 2 m1 ( 2 m  1 ) )  (1 2  2 m1 ) (d1  d 2  d r )  (2 m  1)  (a)
(1)
となる。
a  2 m 1 は素数で無いと仮定しているので、 a は 1 と a 以外に約数をもつので、
 (a)  1 a  2 m となるので、 (1) とあわせて
 (n)  2 m (2 m  1)
m
m
が得られるが、 n が完全数であるので  (n )  2 n  2 ( 2  1 ) となり、矛盾する。
m
故に、 a  2 1 は素数でなければならない。
█
実は、偶数の完全数は n  2
れました。
m1
( 2 m  1) の形しかありません。これはオイラーによって証明さ

Download Report