約数の総和を求める二つの公式と証明

この記事では,正の整数の約数の総和を計算する公式を解説します。入試でも頻出の必須公式です。 約数の総和公式

なお,約数の個数に関しては約数の個数の公式と平方数の性質を参照して下さい。

約数の総和公式と例題

約数の総和公式1

正の整数 nnn=paqbn=p^{a}q^{b}\cdots と素因数分解されているとき,nn の約数の総和は,

(1+p+p2++pa)(1+q+q2++qb)(1+p+p^2+\cdots +p^{a})(1+q+q^2+\cdots +q^{b})\cdots

一般形で書くと難しそうですね。例題で理解しましょう。

例題1

1212 の約数の総和を求めよ。

解答

12=22312=2^2\cdot 3 と素因数分解できるので,約数の総和公式より,

(1+2+22)(1+3)=74=28(1+2+2^2)(1+3)=7\cdot 4=28

ちなみに,1212 の約数を素直に全部足すと,

1+2+3+4+6+12=281+2+3+4+6+12=28

となり,確かに 2828 になりました。

例題2

18001800 の約数の総和を求めよ。

解答

1800=2332521800=2^3\cdot 3^2\cdot 5^2 と素因数分解できるので,上の公式より

(1+2+22+23)(1+3+32)(1+5+52)=15×13×31=6045(1+2+2^2+2^3)(1+3+3^2)(1+5+5^2)\\ =15\times 13\times 31=6045

例題1の 1212 くらいなら約数を列挙して足し算してもよいですが,例題2のように数が大きくなると総和公式が必須です。

練習問題

10001000 の約数の総和を求めよ。

解答

1000=23×531000=2^3\times 5^3 と素因数分解できるので,上の公式より

(1+2+22+23)(1+5+52+53)=15×156=2340(1+2+2^2+2^3)(1+5+5^2+5^3)\\ =15\times 156=2340

→高校数学の問題集 ~最短で得点力を上げるために~のT30でも約数の総和をもとめる問題を解説しています。

公式の証明

約数の総和公式を証明します。

例えば 1212 に対する約数の総和公式 (1+2+22)(1+3)(1+2+2^2)(1+3) を展開してみると,

11+13+21+23+221+223=1+3+2+6+4+121\cdot 1+1\cdot 3+2\cdot 1+2\cdot 3+2^2\cdot 1+2^2\cdot 3\\ =1+3+2+6+4+12

となり,各項が 1212 の約数になっています。どんな場合でも 約数の総和公式の式を展開したときの各項nn の約数が一対一に対応していることを確認すればOKです。

証明

n=p1a1p2a2pkakn=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} と素因数分解されるとする。

nn の約数は p1b1p2b2pkbkp_1^{b_1} p _2^{b_2}\cdots p_k^{b_k} (ただし,各 ii に対して bib_i0biai0\leqq b_i\leqq a_i を満たす整数)という形の整数だけであり,これで全ての約数を表せる。

よって 約数の総和公式の式を展開したときの各項nn の約数が一対一に対応しているので成立する。

応用

  • 等比数列の和の公式を用いることで約数の総和公式を以下のように書くことができます:
    p1a1+11p11p2a2+11p21pkak+11pk1\dfrac{p_1^{a_1+1}-1}{p_1-1}\cdot\dfrac{p_2^{a_2+1}-1}{p_2-1}\cdot \cdots \cdot\dfrac{p_k^{a_k+1}-1}{p_k-1}

  • 約数の総和公式を応用することで偶数の完全数を特徴付けられます。→完全数の性質

二つ目の公式

ここから一気にレベルが上がります。美しいですが,覚える必要はありません,興味のある方のみどうぞ。

約数の総和公式2

nn の約数の総和は,

s=1nt=1scos2πtns\displaystyle\sum_{s=1}^n\sum_{t=1}^s\cos\dfrac{2\pi tn}{s}

三角関数が登場して非常に面白いですが,n(n+1)2\dfrac{n(n+1)}{2} 個のコサインの和を計算しないといけないので全く実用的ではありません。

33 の約数の総和は,

  • s=1s=1 の部分: cos6π=1\cos 6\pi=1
  • s=2s=2 の部分: cos3π+cos6π=0\cos 3\pi +\cos 6\pi=0
  • s=3s=3 の部分: cos2π+cos4π+cos6π=3\cos 2\pi +\cos 4\pi +\cos 6\pi=3

となり総和は 44 になっている。

公式2の証明の概略

以下の二つを証明すれば十分です:

  1. ssnn の約数のとき t=1scos2πtns=s\displaystyle\sum_{t=1}^s\cos\dfrac{2\pi tn}{s}=s

  2. ssnn の約数でないとき t=1scos2πtns=0\displaystyle\sum_{t=1}^s\cos\dfrac{2\pi tn}{s}=0

証明

1を証明する。ns\dfrac{n}{s} が整数のとき,cos2πtns=1\cos\dfrac{2\pi tn}{s}=1 となるので 11ss 個足すことになるのでOK。

2を証明する。複素指数関数を使う。cos2πtns=Re(ei2πtns)\cos\dfrac{2\pi tn}{s}=\mathrm{Re}(e^{i\tfrac{2\pi tn}{s}})

に注意して三角関数の和と等比数列の公式で使ったテクニックを使うと 00 になることが導ける。

役に立たないけどきれい!という公式もけっこう好きです。