2015/01/02

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

分野: 整数問題  レベル: 基本公式

正の整数の約数の総和を表す公式を二つ紹介します。一つ目は入試でも頻出の必須公式です。

二つ目はコサインとか出てくる観賞用の公式です。玄人向け。

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

約数の総和公式と例題

正の整数 $n$ が $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ と素因数分解されているとき,$n$ の約数の総和は,$(1+p_1+p_1^2+\cdots +p_1^{a_1})(1+p_2+p_2^2+\cdots +p_2^{a_2})\cdots$

一般形で書くと仰々しいので例題をどうぞ。

例題

$12$ の約数の総和を求めよ

解答1:$12$ の約数を素直に全部足すと,
$1+2+3+4+6+12=28$

解答2:$12=2^2\cdot 3$ と素因数分解できるので,上の公式より,
$(1+2+2^2)(1+3)=7\cdot 4=28$


$12$ くらいなら解答1でもよいですが,数字が大きくなると総和公式が必須になります。

例題2

$1800$ の約数の総和を求めよ

解答

$1800=2^3\cdot 3^2\cdot 5^2$ と素因数分解できるので,上の公式より
$(1+2+2^2+2^3)(1+3+3^2)(1+5+5^2)=15\cdot 13\cdot 31=6045$

公式の証明

約数の個数の公式を一般的に証明しておきます。

証明

$n$ の約数は $p_1^{b_1} p
_2^{b_2}\cdots p_k^{b_k}$(ただし,各 $i$ に対して $b_i$ は $0\leq b_i\leq a_i$ を満たす整数)という形の整数だけであり,これで全ての約数を表せる。
よって「約数の総和公式の式を展開したときの各項」と「 $n$ の約数」が一対一に対応しているので成立する。

例えば $12$ に対する約数の総和公式$(1+2+2^2)(1+3)$ を展開してみると,
$1\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$
となり,各項が $12$ の約数になっています。

応用

等比数列の和の公式を用いることで約数の総和公式を以下のように書くことができます:
$\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}$

・約数の総和公式を応用することで偶数の完全数の特徴付けを与えることができます。→完全数の性質

二つ目の公式

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

$n$ の約数の総和は,
$\displaystyle\sum_{s=1}^n\sum_{t=1}^s\cos\dfrac{2\pi tn}{s}$

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

$3$ の約数の総和は,
$s=1$ の部分:$\cos 6\pi=1$
$s=2$ の部分:$\cos 3\pi +\cos 6\pi=0$
$s=3$ の部分:$\cos 2\pi +\cos 4\pi +\cos 6\pi=3$
となり総和は $4$ になっています。

証明の概略

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

1:$s$ が $n$ の約数のとき $\displaystyle\sum_{t=1}^s\cos\dfrac{2\pi tn}{s}=s$
2:$s$ が $n$ の約数でないとき $\displaystyle\sum_{t=1}^s\cos\dfrac{2\pi tn}{s}=0$

証明

1について。 $\dfrac{n}{s}$ が整数のとき,$\cos\dfrac{2\pi tn}{s}=1$ となるので $1$ を $s$ 個足すことになるのでOK。

2について。複素指数関数を使う。 $\cos\dfrac{2\pi tn}{s}=\mathrm{Re}(e^{i\tfrac{2\pi t}{s}})$
に注意して三角関数の和と等比数列の公式で使ったテクニックを使うと $0$ になることが導ける。

役に立たないけどきれい!という公式もけっこう好きです。
分野: 整数問題  レベル: 基本公式