乗法的関数

著者:梅谷武
語句:メービウス,乗法的,完全乗法的,完全数,奇素数,メルセンヌ素数

乗法的関数について述べる。

作成:2006-06-15
更新:2021-03-17

オイラーのφ関数のように正の整数上で定義された関数は数論的関数と呼ばれます。数論的関数fが、互いに素であるような正の整数の組m,nに対して、

f(mn) = f(m)f(n)

を満たすとき、乗法的じょうほうてき, multiplicativeであるといいます。任意の正の整数の組m,nに対してこの条件を満たすとき完全乗法的かんぜんじょうほうてき, completely multiplicativeであるといいます。オイラーのφ関数は乗法的で、f(n)=1やf(n)=nは完全乗法的です。

第4章で自然数列のk次の冪和

P_k(n) =

n
∑
i=1

i^k

について考えましたが、この和をnの約数だけに制限したもの

σ_k(n) =

∑
d|n

d^k

について考えてみます。乗法的関数を取り扱うときには

∑
d|n

はnの正の約数に関する和を意味するものと約束します。

具体的に計算してみます。n=2とすると約数は{1,2}ですから、

σ₀(2)=1+1=2, σ₁(2)=1+2=3, σ₂(2)=1+4=5

n=4とすると約数は{1,2,4}ですから、

σ₀(4)=1+1+1=3, σ₁(4)=1+2+4=7, σ₂(4)=1+4+16=21

というようになります。

9以下のσ₀,σ₁,σ₂関数の値を以下に示します。2と3とその積である6のσ₀,σ₁,σ₂の値だけを見ると乗法的になっていることがわかります。

表5.5.5 9以下のσ0,σ1,σ2関数値

n	d\|n	σ₀(n)	σ₁(n)	σ₂(n)
1	1	1	1	1
2	1,2	2	3	5
3	1,3	2	4	10
4	1,2,4	3	7	21
5	1,5	2	6	26
6	1,2,3,6	4	12	50
7	1,7	2	8	50
8	1,2,4,8	4	15	85
9	1,3,9	3	13	91

正の整数nの素因数分解を

n = p₁^e_p₁(n)p₂^e_p₂(n) ⋯ p_r^e_{p_r}(n)

としたときに、σ_k(n)を書き下すことができます。k=0のときσ₀(n)はnの正の約数の個数を意味しますが、nの正の約数が

{ p₁^a₁p₂^a₂ ⋯ p_r^a_r | 0≦a_i≦e_{p_i}(n) }

で尽くされることから、

(5.1)

σ₀(n) = (e_p₁(n)+1)(e_p₂(n)+1) ⋯ (e_{p_r}(n)+1)

が成り立ちます。k>0のときはnの正の約数の集合の各元をk乗して和をとると、

σ_k(n) =

∑
0≦a_i≦e_{p_i}(n), i=1,⋯,r

p₁^a₁kp₂^a₂k ⋯ p_r^a_rk

となります。この右辺は

1+p_i^k+p_i^2k+ ⋯ + p_i^e_{p_i}(n)k =

p_i^{(e_{p_i}(n)+1)k} － 1

p_i^k － 1

をi=1,⋯,rに関して掛けたものに等しいですから、

(5.2)

σ_k(n) =

r
∏
i=1

p_i^{(e_{p_i}(n)+1)k} － 1

p_i^k － 1

が成り立ちます。この公式の形からσ_k(n)が乗法的であることが自然に導かれます。

完全数とメルセンヌ素数

σ(n)=σ₁(n)はn自身を含む約数の和を表わしています。σ(n)=2nとなる数は完全数かんぜんすう, perfect numberと呼ばれ、古代から研究されてきました。ユークリッド原論第IX巻の最後の命題は次のようなものになっています。

命題5.5.8

もし2ⁿ－1, n > 1が素数ならば、2^n－1(2ⁿ－1)は完全数である。

証明

p=2ⁿ－1, N=2^n－1pとおき、σ(N)=2Nを示す。

σ(N) =

2ⁿ－1

2－1

⋅

p²－1

p－1

= (2ⁿ－1)(p+1) = 2ⁿ(2ⁿ－1) = 2N.

■

この命題によって2ⁿ－1の形の素数を見つければ、それに2^n－1をかけることによって完全数を得ることができます。したがって、この形の新しい素数を見つければ、それと同時に新しい完全数が見つかることになります。古代ギリシャにおいては6,496,8128という三つの完全数が発見されています。

17世紀中頃のフェルマー、メルセンヌ、フレニクル、デカルト等により交わされた書簡から、当時の科学アカデミーにおいて完全数を含むさまざまな数探しが流行していたことがわかります。

フェルマーは1640年6月のメルセンヌ宛書簡の中で2ⁿ－1の形の素数の探索に関する三つの命題について書いています。一つ目は2ⁿ－1が素数であれば、nは素数でなければならないということです。これはn=abと1より大きい二つの数に分解されれば、

2ⁿ － 1 = (2^a － 1)(2^a(b－1) + 2^a(b－2) + ⋯ + 2^a + 1)

となることからわかります。二つ目はpが奇素数きそすう, odd prime numberのときp | 2^p－1－1となるということです。これは

2^p－1 ≡ 1 (mod p)

と書くことができます。三つ目はpが素数であるときqが2^p－1の素因数であればp | q－1であるというものです。これは

2^p ≡ 1 (mod q) ⇒ p | q－1

と書くことができ、既約剰余類群(ℤ/qℤ)^×における2の位数が全体の位数q－1の約数であるということを意味しています。その後、フェルマーはこれらの命題をフェルマーの小定理にまで一般化して1640年10月18日付けのフレクニル宛の書簡に書いたことは前節で述べました。

フェルマーは次の例でこの判定法の使い方を説明しています。

例題5.5.14

2³⁷－1は素数ではないことを示せ。

qを2³⁷－1の素因数とすれば37|q－1より、q=37k+1, k＞1ですが、kが奇数ならばqは偶数となるのでkは偶数でなければなりません。したがってq=74k+1, k＞1となることがわかります。k=1のときq=75は素数ではありません。k=2のときq=149となり素数ですが、

2³⁷－1 = 137438953471 = 922409083 * 149 + 104

となり割り切れません。k=3のときq=223となり、これは素数であって

2³⁷－1 = 137438953471 = 616318177 * 223

と割れますので2³⁷－1は素数ではありません。

メルセンヌは1644年に『Cogitata Physica-Mathematica(物理数学思索)』の中で2ⁿ－1は

n = 2,3,5,7,13,17,19,31,67,127,257

に対して素数であり、これ以外の257未満の正の整数については合成数であると述べました。この記述により2ⁿ－1の形の素数はメルセンヌ素数めるせんぬそすう, Mersenne prime numberと呼ばれるようになりましたが、この主張には誤りがありました。この範囲では

n = 2,3,5,7,13,17,19,31,61,89,107,127

に対して素数になることが実証されたのは計算機が発達した20世紀になってからのことです。

オイラーは偶数の完全数が命題5.5.8の形のものに限ることを証明しました。

命題5.5.18

偶数の完全数は2^n－1(2ⁿ－1), (n > 1, 2ⁿ－1は素数)という形のものに限る。

証明

偶数の完全数aをa=2^e－1b, (2,b)=1, e＞1と分解する。

σ(a) = σ(2^e－1)σ(b) = (2^e－1)σ(b)

である。一方、σ(a)=2a=2^ebであるから、(2^e－1)σ(b)=2^ebより、

σ(b) = b +

2^e－1

となる。e＞1よりb/(2^e－1)はbの真の約数であり、σ(b)はbのすべての約数の和であったから、b=2^e－1でかつ素数でなければならない。■

この命題により、偶数の完全数はすべてメルセンヌ素数に対応するということがわかりました。しかし、奇数の完全数についてはそれが存在するかどうかもまだわかっていません。

また、オイラーは次の判定法を残しています。

命題5.5.22

pがp ≡ 3 (mod 4)なる素数であるとき、2p+1が素数であることと

2^p ≡ 1 (mod 2p+1)

は同等である。したがって、2p+1が素数ならば2p+1|2^p－1となり、2^p－1は素数ではない。

この証明については平方剰余の概念を導入してから述べることにします。

メービウスの反転公式

一般に乗法的関数は次の性質をもちます。

命題5.5.25

f(n)が乗法的であれば、次式で定義されるg(n)も乗法的である。

g(n) =

∑
d|n

f(d)

証明

(m,n)=1, d|m, e|nとすると、(d,e)=1であるから、

g(mn) =

∑
a|mn

f(a)

∑
d|m,e|n

f(de)

= (

∑
d|m

f(d)

)(

∑
e|n

f(e)

) = g(m)g(n).

■

f(n)=n^kは完全乗法的関数ですから

σ_k(n) =

∑
d|n

d^k

が乗法的関数であることはこの命題からもわかります。

正の整数nの素因数分解を

n = p₁^e_p₁(n)p₂^e_p₂(n) ⋯ p_k^e_{p_k}(n)

としたときに、メービウスMöbius, August Ferdinand, 1790-1868関数μ(n)を

μ(n) =

n=1

(－1)^k,

すべてのi=1,⋯,kについてe_{p_i}(n)=1

あるi=1,⋯,kについてe_{p_i}(n)＞1

によって定義します。μ(n)は乗法的で、さらにn=p₁p₂⋯p_k＞1ならば

∑
d|n

μ(d)

1 +

∑
i

μ(p_i)

∑
i,j

μ(p_ip_j)

+ ⋯ + μ(p₁ p₂ ⋯ p_k)

k
∑
i=0

(

k
i

)

(－1)ⁱ

= (1－1)^k = 0

ですから、次が成り立ちます。

(5.3)

∑
d|n

μ(d)

n=1

n＞1

このメービウス関数を使うことによって次の反転公式が得られます。

命題5.5.30 メービウスの反転公式

正の整数に対して定義されている関数f(n),g(n)について

g(n) =

∑
d|n

f(d)

ならば、

f(n) =

∑
d|n

μ(n/d)g(d)

∑
d|n

μ(d)g(n/d)

証明

∑
d|n

μ(d)g(n/d)

∑
d|n

μ(d)

∑
a|n/d

f(a)

∑
ad|n

μ(d)f(a)

∑
d|n

f(d)

∑
a|n/d

μ(a)

∑
d|n

μ(n/d)g(d)

上式において

∑
a|n/d

μ(a)

はn=dのときに1で、それ以外は0となるから上式はf(n)に等しい。■

同様にしてこの命題の逆を証明することができます。

命題5.5.33 メービウスの反転公式

正の整数に対して定義されている関数f(n),g(n)について

f(n) =

∑
d|n

μ(n/d)g(d)

ならば、

g(n) =

∑
d|n

f(d)

証明

演習とする。■

オイラーのφ関数については次の式が成り立ちます。

命題5.5.36

(5.4)

∑
d|n

φ(d)

= n

証明

正の整数nの素因数分解をn=p₁^e₁p₂^e₂ ⋯ p_k^e_kとする。nの正の約数全体の集合は{ p₁^a₁p₂^a₂ ⋯ p_r^a_r | 0≦a_i≦e_i }であるから、

∑
d|n

φ(d)

∑
(a_i)

∏
i

φ(p_i^a_i)

∏
i

(1+φ(p_i)+φ(p_i²)+⋯+φ(p_i^e_i))

ここで

1 + φ(p_i) + φ(p_i²) + ⋯ + φ(p_i^e_i)

1 + (p_i－1) + p_i(p_i－1) + ⋯ + p_i^e_i(p_i－1) = p_i^e_i

が成り立つので結論が従う。■

これにメービウスの反転公式を適用すると次の公式が得られます。

(5.5)

φ(n) = n

∑
d|n

μ(d)

∑
d|n

dμ(n/d)

また、

σ_k(n) =

∑
d|n

d^k

に適用すると次の公式が得られます。

(5.6)

n^k =

∑
d|n

μ(n/d)σ_k(d)

参考文献

[1] G.H. ハーディ, E.M. ライト, 数論入門〈1〉, シュプリンガー・フェアラーク東京, 2001

[2] 中村幸四郎, 伊東俊太郎, 寺阪英孝, 池田美恵訳, ユークリッド原論, 共立出版, 1996

[3] アンドレヴェイユ, 数論―歴史からのアプローチ, 日本評論社, 1987

人　　物

メービウス Möbius, August Ferdinand, 1790-1868

数　　学

乗法的じょうほうてき, multiplicative
完全乗法的かんぜんじょうほうてき, completely multiplicative
完全数かんぜんすう, perfect number
奇素数きそすう, odd prime number

奇数の素数のこと。2より大きい素数と考えてもよい。

メルセンヌ素数めるせんぬそすう, Mersenne prime number

Published by SANENSYA Co.,Ltd.