乗法的関数
著者:梅谷 武
語句:メービウス,乗法的,完全乗法的,完全数,奇素数,メルセンヌ素数
乗法的関数について述べる。
作成:2006-06-15
更新:2013-06-14
 オイラーのφ関数のように正の整数上で定義された関数は数論的関数と呼ばれます。数論的関数fが、互いに素であるような正の整数の組m,nに対して、
f(mn) = f(m)f(n)
を満たすとき、乗法的じょうほうてき, multiplicativeであるといいます。任意の正の整数の組m,nに対してこの条件を満たすとき完全乗法的かんぜんじょうほうてき, completely multiplicativeであるといいます。オイラーのφ関数は乗法的で、f(n)=1f(n)=nは完全乗法的です。
 第4章で自然数列のk次の冪和
Pk(n) =
n

i=1
ik
について考えましたが、この和をnの約数だけに制限したもの
σk(n) =
 

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

d|n
nの正の約数に関する和を意味するものと約束します。
 具体的に計算してみます。n=2とすると約数は{1,2}ですから、
σ0(2)=1+1=2, σ1(2)=1+2=3, σ2(2)=1+4=5
n=4とすると約数は{1,2,4}ですから、
σ0(4)=1+1+1=3, σ1(4)=1+2+4=7, σ2(4)=1+4+16=21
というようになります。
 9以下のσ012関数の値を以下に示します。23とその積である6σ012の値だけを見ると乗法的になっていることがわかります。
表5.5.5 9以下のσ0,σ1,σ2関数値
nd|nσ0(n)σ1(n)σ2(n)
11111
21,2235
31,32410
41,2,43721
51,52626
61,2,3,641250
71,72850
81,2,4,841585
91,3,931391
 正の整数nの素因数分解を
n = p1ep1(n)p2ep2(n) ⋯ prepr(n)
としたときに、σk(n)を書き下すことができます。k=0のときσ0(n)nの正の約数の個数を意味しますが、nの正の約数が
{ p1a1p2a2 ⋯ prar | 0≦ai≦epi(n) }
で尽くされることから、
(5.1)
σ0(n) = (ep1(n)+1)(ep2(n)+1) ⋯ (epr(n)+1)
が成り立ちます。k>0のときはnの正の約数の集合の各元をk乗して和をとると、
σk(n) =
 

0≦ai≦epi(n), i=1,⋯,r
p1a1kp2a2k ⋯ prark
となります。この右辺は
1+pik+pi2k+ ⋯ + piepi(n)k =
pi(epi(n)+1)k - 1
pik - 1
i=1,⋯,rに関して掛けたものに等しいですから、
(5.2)
σk(n) =
r

i=1
pi(epi(n)+1)k - 1
pik - 1
が成り立ちます。この公式の形からσk(n)が乗法的であることが自然に導かれます。

完全数とメルセンヌ素数

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

命題5.5.8

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

証明

p=2n-1, N=2n-1pとおき、σ(N)=2Nを示す。
σ(N) =
2n-1
2-1
p2-1
p-1
= (2n-1)(p+1) = 2n(2n-1) = 2N.
 この命題によって2n-1の形の素数を見つければ、それに2n-1をかけることによって完全数を得ることができます。したがって、この形の新しい素数を見つければ、それと同時に新しい完全数が見つかることになります。古代ギリシャにおいては6,496,8128という三つの完全数が発見されています。
 17世紀中頃のフェルマー、メルセンヌ、フレニクル、デカルト等により交わされた書簡から、当時の科学アカデミーにおいて完全数を含むさまざまな数探しが流行していたことがわかります。
 フェルマーは1640年6月のメルセンヌ宛書簡の中で2n-1の形の素数の探索に関する三つの命題について書いています。一つ目は2n-1が素数であれば、nは素数でなければならないということです。これはn=ab1より大きい二つの数に分解されれば、
2n - 1 = (2a - 1)(2a(b-1) + 2a(b-2) + ⋯ + 2a + 1)
となることからわかります。二つ目はp奇素数きそすう, odd prime numberのときp | 2p-1-1となるということです。これは
2p-1 ≡ 1 (mod p)
と書くことができます。三つ目はpが素数であるときq2p-1の素因数であればp | q-1であるというものです。これは
2p ≡ 1 (mod q) ⇒ p | q-1
と書くことができ、既約剰余類群(ℤ/qℤ)×における2の位数が全体の位数q-1の約数であるということを意味しています。その後、フェルマーはこれらの命題をフェルマーの小定理にまで一般化して1640年10月18日付けのフレクニル宛の書簡に書いたことは前節で述べました。
 フェルマーは次の例でこの判定法の使い方を説明しています。

例題5.5.14

237-1は素数ではないことを示せ。
q237-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となり素数ですが、
237-1 = 137438953471 = 922409083 * 149 + 104
となり割り切れません。k=3のときq=223となり、これは素数であって
237-1 = 137438953471 = 616318177 * 223
と割れますので237-1は素数ではありません。
 メルセンヌは1644年に『Cogitata Physica-Mathematica(物理数学思索)』の中で2n-1
n = 2,3,5,7,13,17,19,31,67,127,257
に対して素数であり、これ以外の257未満の正の整数については合成数であると述べました。この記述により2n-1の形の素数はメルセンヌ素数めるせんぬそすう, Mersenne prime numberと呼ばれるようになりましたが、この主張には誤りがありました。この範囲では
n = 2,3,5,7,13,17,19,31,61,89,107,127
に対して素数になることが実証されたのは計算機が発達した20世紀になってからのことです。
 オイラーは偶数の完全数が命題5.5.8の形のものに限ることを証明しました。

命題5.5.18

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

証明

 偶数の完全数aa=2e-1b, (2,b)=1, e>1と分解する。
σ(a) = σ(2e-1)σ(b) = (2e-1)σ(b)
である。一方、σ(a)=2a=2ebであるから、(2e-1)σ(b)=2ebより、
σ(b) = b +
b
2e-1
となる。e>1よりb/(2e-1)bの真の約数であり、σ(b)bのすべての約数の和であったから、b=2e-1でかつ素数でなければならない。■
 この命題により、偶数の完全数はすべてメルセンヌ素数に対応するということがわかりました。しかし、奇数の完全数についてはそれが存在するかどうかもまだわかっていません。
 また、オイラーは次の判定法を残しています。

命題5.5.22

pp ≡ 3 (mod 4)なる素数であるとき、2p+1が素数であることと
2p ≡ 1 (mod 2p+1)
は同等である。したがって、2p+1が素数ならば2p+1|2p-1となり、2p-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)=nkは完全乗法的関数ですから
σk(n) =
 

d|n
dk
が乗法的関数であることはこの命題からもわかります。
 正の整数nの素因数分解を
n = p1ep1(n)p2ep2(n) ⋯ pkepk(n)
としたときに、メービウスMöbius, August Ferdinand, 1790-1868関数μ(n)
μ(n) = lc96
1,
n=1
(-1)k,
すべてのi=1,⋯,kについてepi(n)=1
0,
あるi=1,⋯,kについてepi(n)>1
によって定義します。μ(n)は乗法的で、さらにn=p1p2⋯pk>1ならば
          
 

d|n
μ(d)
=
1 +
 

i
μ(pi)
+
 

i,j
μ(pipj)
+ ⋯ + μ(p1 p2 ⋯ pk)
=
k

i=0
(k
i
)
(-1)i
= (1-1)k = 0
ですから、次が成り立ちます。
(5.3)
 

d|n
μ(d)
= lc48
1,
n=1
0,
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)
=
lb36
 

d|n
μ(d)
rb36lb36
 

a|n/d
f(a)
rb36
=
 

ad|n
μ(d)f(a)
=
lb36
 

d|n
f(d)
rb36lb36
 

a|n/d
μ(a)
rb36
=
 

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=p1e1p2e2 ⋯ pkekとする。nの正の約数全体の集合は{ p1a1p2a2 ⋯ prar | 0≦ai≦ei }であるから、
 

d|n
φ(d)
=
 

(ai)
 

i
φ(piai)
=
 

i
(1+φ(pi)+φ(pi2)+⋯+φ(piei))
ここで
               
1 + φ(pi) + φ(pi2) + ⋯ + φ(piei)
=
1 + (pi-1) + pi(pi-1) + ⋯ + piei(pi-1) = piei
が成り立つので結論が従う。■
 これにメービウスの反転公式を適用すると次の公式が得られます。
(5.5)
φ(n) = n
 

d|n
μ(d)
d
=
 

d|n
dμ(n/d)
また、
σk(n) =
 

d|n
dk
に適用すると次の公式が得られます。
(5.6)
nk =
 

d|n
μ(n/d)σk(d)

参考文献

[1] G.H. ハーディ, E.M. ライト, 数論入門〈1〉, シュプリンガー・フェアラーク東京, 2001
img
高木貞治, 遠山啓の本で学んだ後で読むと、初等整数論の別の側面を見ることができて新鮮に感じます。歴史的な記述や詳細な文献表があり、日本語で読める数学史の資料としても貴重です。
 
[2] ユークリッド(渡邉研究室訳), ユークリッド原論, 山口大学教育学部数理情報教室, 2003
[3] 中村幸四郎, 伊東俊太郎, 寺阪英孝, 池田美恵 訳, ユークリッド原論, 共立出版, 1996
[4] アンドレ ヴェイユ, 数論―歴史からのアプローチ, 日本評論社, 1987
img
 
 
人  物
メービウス Möbius, August Ferdinand, 1790-1868
 
数  学
乗法的 じょうほうてき, multiplicative
完全乗法的 かんぜんじょうほうてき, completely multiplicative
完全数 かんぜんすう, perfect number
奇素数 きそすう, odd prime number
奇数の素数のこと。2より大きい素数と考えてもよい。
メルセンヌ素数 めるせんぬそすう, Mersenne prime number
 
Published by SANENSYA Co.,Ltd.