 | べき乗演算子^は四則演算より優先度が高いものとします。
n ≧ 2なので、nは1個以上の素因数を持ちます。m = ω(n)とすればmは自然数です。
nの素因数を小さい方からp[1], p[2], ・・・, p[m]とします。
また、各素因数の指数をe[1], e[2], ・・・, e[m]とすると、
n = Π[k=1,m]{p[k]^e[k]}・・・・・(1)
となります。
n自身を含めたnの正の約数の和は、
τ(n)+n = Π[k=1,m]{(p[k]^(e[k]+1)-1)/(p[k]-1)}・・・・・(2)
となります。
(1)(2)より、以下が示せれば良いことになります。
τ(n)+n < nm+n
⇒ Π[k=1,m]{(p[k]^(e[k]+1)-1)/(p[k]-1)} < (m+1)Π[k=1,m]{p[k]^e[k]}
⇒ Π[k=1,m]{(p[k]-1/(p[k]^e[k]))/(p[k]-1)} < m+1・・・・・(3)
ここで、p[1] ≧ 2, p[2] ≧ 3, ・・・, p[m] ≧ m+1ですので、
(p[k]-1/(p[k]^e[k]))/(p[k]-1) < p[k]/(p[k]-1) = 1+1/(p[k]-1) ≦ 1+1/((k+1)-1) = (k+1)/k
であり、これを(3)に適用すると、
Π[k=1,m]{(p[k]-1/(p[k]^e[k]))/(p[k]-1)} < Π[k=1,m]{(k+1)/k} = m+1
となり、(3)が成立することが分かります。
|
このトピックをツリーで一括表示