約数関数
約数関数とは、約数の総和を返す関数のことです。
定義をきちんと書くと、下記のようになります。
自然数nに対し、そのnの約数全ての総和を返す関数を約数関数と呼び、σ(n)で表す。
例えば、
σ(1)=1
σ(2)=1+2=3
σ(3)=1+3=4
σ(4)=1+2+4=7
σ(5)=1+5=6
σ(6)=1+2+3+6=12
σ(7)=1+7=8
σ(8)=1+2+4+8=15
σ(9)=1+3+9=13
σ(10)=1+2+5+10=18
σ(11)=1+11=12
σ(12)=1+2+3+4+6+12=28
σ(13)=1+13=14
σ(14)=1+2+7+14=24
σ(15)=1+3+5+15=24 //注目σ(14)と同じ （※)
という具合になります。
（※)たまたま気がつきました。連続して約数の和が同じになっている最初のところになります。
素数ベキに対するの約数関数
pをある素数とし、kを自然数とします。
\(n=p^k\)に対して、約数関数の値を調べてみましょう。
素因数分解ができれば、約数を全て書き表すことができるため、約数関数の値を求めることができます。
\(n=p^k\)の素因数は\(p\)ただ一つであり、その約数は、
\(1,p,p^2,p^3,…,p^k\)で全てですから、その総和は、
\(1+p+p^2+p^3+…+p^k\)であって、これは初項1、公比pの等比数列の和です。
したがって等比数列の和の公式から、
\[σ(p^k)=\sum_{i=0}^{k} p^i=\frac{p^{k+1}-1}{p-1}\]
という公式が得られます。
約数関数の乗法性
乗法性とは、積を保存するという意味です。
つまり、
\[σ(ab)=σ(a)σ(b)\]
ただ、約数関数の場合、注意が必要です。
いつも、\(σ(ab)=σ(a)σ(b)\)とは限らないからです。
乗法的でない反例
σ(2*2)=7, σ(2)=3, σ(2)σ(2)=9
∴σ(2*2)≠σ(2)σ(2)
これは、自然数a,bが互いに素な場合に成立します。
改めて約数関数の情報性を記載しますと、
自然数a,bに対し
aとbが互いに素であれば
\(σ(ab)=σ(a)σ(b)\)
乗法的な例
いくつか確かめてみます。
\( σ(2*3)=σ(2)σ(3)=12 \)
成立していますね。
証明は、nがpのべき乗の時と同じように、素因数分解して約数を列挙すればわかります。
これを一般の形で書くと、
\[σ(p_1^{k_1}p_2^{k_2}…p_m^{k_m})=σ(p^{k_1})σ(p^{k_2})…σ(p^{k_m})\]
\[ =\frac{p_1^{k_1+1}-1}{p_1-1} \frac{p_1^{k_2+1}-1}{p_2-1} … \frac{p_1^{k_m+1}-1}{p_m-1}\]
となります。
これが約数関数の公式です。
例題
自然数360のすべての約数の和を求めよ。
例題の解き方
360を素因数分解します。やり方は、素因数分解のコツ。
\(360=2^3 3^2 5\)なので、
上記の公式を使うと
\(\frac{2^4-1}{2-1} \frac{3^3-1}{3-1} \frac{5^2-1}{5-1}\)
\(=15 * 13 * 6 \)
\(1170\)
答え 360のすべての約数の和は、1170
約数の個数
実は、約数の総和ではなく、約数の個数も素因数分解からわかります。
指数部分に１を足してかければ求まります。
360の例で説明しますと、
\(360=2^3 3^2 5\)なので、約数の個数は、
\((3+1)(2+1)(1+1)=4*3*2=24\)
360の約数の個数は24個。
実際にかいてみると、この約数の書き方をよく観察すれば上記の式がわかると思います。
約数をそれぞれ素因数分解して書いた方がわかりよいのですが、長い式になるので、下記は素因数分解せずに約数を書いています。
\(1,2,4,8,\) \(3,6,12,24,\) \(9,18,36,72,\) \(5,10,20,40,\) \(15,30,60,120,\) \(45,90,180,360,\)
でちゃんと24個ありました。
約数関数の拡張σx(n)
拡張された約数関数して、約数のx乗の総和を表すσx(n)という関数があります。上で述べた約数の総和を表す関数σ(n)はx=1の場合のσx(n)で、x=0にするとσx(n)は約数の個数を返します。
自然数nに対し、「そのnの約数それぞれのx乗」の全ての総和を返す関数を約数関数と呼び、σx(n)で表す。
[ad#foot]
