1. No category

情報数学 Ⅰ 配布日時 2014 年 7 月 7 日
今後の予定
１４回７月１４日 講義
１５回７月２１日 講義＆模擬試験＆授業アンケート
定期試験７月２８日(月) 10:55~12:05 教室 20831
自筆ノートのみ持ち込み可、講義のプリント等の印刷物は持ち込み不可
定理 5.8 ( オイラー)
n が偶数の完全数ならば, n  2 m1 ( 2 m  1) , m  N , M m  2 m  1 ( メルセンヌ素数) の
形である。
証明
n は偶数なので、ある自然数 m, a が存在して、
n  2 m1 a 、 gcd( a, 2)  1
m1
と書ける。 a の約数を d1 ,, d r とすると、 n  2 a のすべての約数は
d1 , 2 d1 , , 2 m1 d1 ,
d 2 , 2 d 2 , , 2 m1 d 2 ,
,
, 2 m1 d r
dr , 2 dr ,
となる。
a の約数の総和は  (a )  d1  d 2    d r なので、
n の約数の総和  (n ) は
 (n)  (1 2  2 m1 ) (d1  d 2  d r )  (2 m  1)  (a)
(1)
となる。
他方、 n が完全数であるので  (n )  2 n  2 a となり、
m
( 2 m  1)  ( a)  2 m a
(2)
が得られる。これより、 2  1 は 2 a を割り切る。
m
m
ところが、 gcd( 2  1, 2)  1 なので、 2  1 は
m
m
a を割り切るので、
ある自然数 b が存在し、 a  b (2  1)
ここで、もし b 1 と仮定すると、
m
となる。
a  b (2 m  1) の約数として 1, b, 2 m  1, b (2 m  1) は存在する。
m
m
m
m
すると、  (a )  1  b  (2  1)  b(2 1)  2 (1  b)  2 b
2m a
 2m b
m
2 1
となり、矛盾であるので、 b 1 でなければならない。
 (a) 
以上より、 a  2  1 となり、 n  2
m
m1
(2 m  1) が得られる。
2 m  1が素数となるのは、この前の定理により証明されている。
█
情報数学 Ⅰ 配布日時 2014 年 7 月 7 日
定理 5.9
奇数の自然数 n に対して、素因子 p が全て p  3 mod 4 を満たせば、
n は完全数ではない。
n  p1 1 p2 2  pl l と素因数分解されるとする。
e
証明 背理法：
e
e
もし奇数の自然数 n を完全数とすると、  (n)  2 n
を満たしているので、
2n   (n)   ( p1 1 )  ( p2 2 )   ( pl l )
e
e
e
左辺は 2n と奇数 n なので、 2n mod 4  2 となる。
辺は、 ( p1 1 )  1  p1  p1    p1 1
e
2
e
であるので、e1 が偶数なら  ( p1 1 ) mod 4  1
e
であり、
e1 が奇数なら、 p1  3 mod 4 なので、  ( p1 1 ) mod 4  0 となる。
つまり、右辺は mod 4 で、0 又は 1 となるので、矛盾する。
故に、奇数の自然数 n が存在すれば、そのある素因子 p で p  1 mod 4 なるものが存在す
e
る。
■
定理 5.10
奇数の自然数 n が平方数をもたなければ、完全数ではない。
証明
n は平方因子をもたないので
n  p1 p2  pk
と書けるが、これまでの議論で k  3 としてよい。
もし奇数の自然数 n が完全数ならば、
2 n   (n)   ( p1 )  ( p2 )   ( pk )
となり、  ( p1 )  1 p1 は素因数を１つ以上もつので、
右辺は、2
k
( k  3 )で割り切れる。所が、左辺には２の素因子は 1 つしかない。
故に、奇数の自然数 n が平方数をもたなければ、完全数ではない。■
次の定理は, オイラーが証明したと伝えられている有名な結果です。
情報数学 Ⅰ 配布日時 2014 年 7 月 7 日
定理 5.11 (オイラー)
n が奇数の完全数ならば, その素因数分解は次のようになる。

n  p0 0 p1e1  pkek ,
p0   0  1 mod 4
e1    ek  0 mod 2
p0 , p1, pk は相異なる素数
証明
奇数 n の素因数分解を

n  p0 0 p1e1  pkek
とすると、
 (n)   ( p0 )  ( p1e )   ( pk e )
0
1
k
奇数 n を完全数とすると  (n)  2 n

なので、
2 n   ( p0 0 )  ( p1 1 )   ( pk k )
e
e
n は奇数なので、 2n mod 4  2 となる。
従って、
 ( p0 )  ( p1e )   ( pk e )  2 mod 4
0
1
k
となり、
 ( p0 )  2 mod 4
0
 ( pi )  1 mod 2 ， i  1,, k
i
と言ったようになる。
ここで、  ( p )  1 p  p    p に注意すると、
e
2
 ( p )  2 mod 4

 ( pe )  1 mod 2

であるので、証明された。
e
p    1 m o 4d
e  0 m o 2d
■
情報数学 Ⅰ 配布日時 2014 年 7 月 7 日
【過剰数と不足数】
・過剰数
過剰数は、自然数で、その正の約数の総和が元の数の 2 倍より大きい数のことである。
約数関数を使うと、自然数 n が  (n)  2n を満たせば、 n は過剰数である。
例えば 20 の約数の総和は 1+2+4+5+10+20=42>20×2 であるので 20 は過剰数である。全て
合成数で無数に存在し、そのうち最小のものは 12 である。
過剰数を 12 から小さい順に列記すると
12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, …
奇数の過剰数のうち最も小さい数は 945 である（  (945)  1920  2  945 。
過剰数もしくは完全数の倍数は全て過剰数であり、したがって偶数の過剰数も奇数の過剰数も
無数に存在する。また全ての擬似完全数は完全数もしくは過剰数である。ほとんどの過剰数は擬
似完全数でもあり、そうでない過剰数は不思議数とよばれる。
 (n)  2n  1 を満たす n は過剰数であり、準完全数とよばれる。このような数は未だに見付
かっておらず、もし存在するなら奇数の平方数で 10
35
より大きく、少なくとも 7 つの素因子を
持つことが分かっている。
・自然数のうち過剰数が占める割合は 0.2474 から 0.2480 の間であると証明されている。
・20161 より大きい整数は 2 つの過剰数の和で表すことができる。
・20 が過剰数なので、
その倍数つまり下 2 桁が 00,20,40,60,80 である数は全て過剰数となる。
・不足数
不足数は、自然数のうち、その正の約数の総和が元の数の 2 倍より小さい数のことである。
約数関数を使うと、自然数 n が  (n)  2n を満たせば、 n は不足数である。
例えば 15 の約数の総和は 1+3+5+15=24<15×2 であるので 15 は不足数である。不足数は無数に
存在し、そのうち最小のものは 1 である。
不足数を 1 から小さい順に列記すると
1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 21, 22, 23, 25, 26, 27, 29,
31, …
全ての素数 p は約数の和が  ( p)  1  p  2 p である不足数である。さらに、自然数 e に対し
e
て、 p を考えると、
情報数学 Ⅰ 配布日時 2014 年 7 月 7 日
2 pe   ( pe )  2 pe 
p e 1
1

p e ( p  2)  1  0
p 1 p 1


e
となり、 p は不足数である。
また素数 p  5 を 2 倍した偶数 2 p の約数の和は  (2 p)  1  2  p  2 p  2  2 p となるの
で不足数である。素数は無数にあるので偶数の不足数も奇数の不足数も無数に存在する。また不
足数や完全数の約数は全て不足数となる。
 (n)  2n  1 を満たす n は不足数であり、概完全数とよばれる。概完全数は無数にありその
k
うち最も小さいものは 1 であるが、2 の累乗数 2 の形をした数しか見つかっておらず他の形を
した概完全数があるのかどうかは分かっていない。
補題 5.12
自然数 e, j と素数 p に対して、
p j  ( p e )   ( p e j )
が成り立つ。
証明
p j  ( p e )  p j (1 p  p 2  p e )  p j  p j 1  p j e
 1  p  p 2   p j  p j 1  p j e  ( p e j )
与式が成立する。
■
補題 5.13
自然数 n, m に対して、 m は n の約数で m n ならば、
n
 ( n)

m
 ( m)
が成り立つ。
証明
m の素因数分解を
m  p1e1 p2 2  pkek
e
とすると、非負整数 t1 , t 2 , , t k と p1 , p2 , , pk と互いに素な自然数 a が存在して、
e  t2
n  p1e1  t1 p2 2
 pkek  t k a
と書ける。
m n なので、t1 , t 2 , , t k のどれかが 0 でないか、a 1 のいずれかが成り立つ。
情報数学 Ⅰ 配布日時 2014 年 7 月 7 日
n
 p1t1 p2t 2  pkt k a
m
さらに、
である。
e j
j
e
前述の補題より、自然数 e, j と素数 p に対して、  ( p )  p  ( p )
 (n)   ( p1e  t )  ( p2e
1
1
2
 t2
)   ( pkek  t k )  ( a)
 p1 1  ( p1e1 ) p2 2 ( p2 2 )  pk k  ( pkek ) a
t
t
e
t
 p1t1 p2 2  pkt k a  ( p1e1 p2 2  pkek )
t

e
n
 (m)
m
より、与式が成立する。
■
定理 5.14
自然数 n が過剰数なら n の倍数も過剰数である。
証明
n の任意の倍数を n ' とすると前述の補題より、
n'
 ( n)
等号は、１の倍数を考慮。
n
n は過剰数なので、  (n )  2n となり、
 (n ' ) 
n'
2 n  2 n'
n
となるので、 n ' も過剰数となる。
 (n ' ) 
■
定理 5.15
自然数 n が不足数なら n の約数も不足数である。
証明
n の任意の約数を m とすると前述の補題より、
m
 ( n)
等号は、約数として n 自身の場合を考慮。
n
が成り立ち、 n は不足数なので  (n)  2 n が成り立つ。
 (m) 
従って、
 (m) 
m
2n  2m
n
となり、約数 m も不足数となる。 ■
となる。
情報数学 Ⅰ 配布日時 2014 年 7 月 7 日
n を完全数とします。 n ' を n 自身を除く倍数とします。 n'  n となっている。
n'
n'
 (n)  2n  2 n' となり、 n ' は過剰数となる。
n
n
また、 m を n の約数(ただし、 n 自身は除く)としますと、
補題より、  (n ' ) 
 (m) 
m
m
 ( n )  2 n  2m
n
n
となるので、m は不足数となる。
つまり, 完全数の自分自身を除く約数は不足数です。
情報数学 Ⅰ 配布日時 2014 年 7 月 7 日