この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

整数論の問題

難易度 2教科書の演習問題レベル証明問題大学数学整数論

正の整数 $m$ に対し、 $τ (m)$ を $m$ の正の約数の個数とする。また、メビウス関数 $μ$ を
$μ (m) = ⎩ ⎨ ⎧ 1 (- 1)^{k} 0 (m = 1) (m が相異なる k 個の素数の積) (m がある素数の 2 乗で割り切れる)$
で定める。

すべての正の整数 $n$ に対して
$d ∣ n \sum μ (d)^{2} τ (\frac{n}{d}) = τ (n^{2})$
が成り立つことを証明せよ。ここで和は $n$ の正の約数 $d$ 全体にわたる。

ただし、素因数分解の一意性と、 $m = q_{1}^{f_{1}} \dots q_{s}^{f_{s}}$ （ $q_{i}$ は相異なる素数、 $f_{i}$ は正の整数）のとき $τ (m) = (f_{1} + 1) \dots (f_{s} + 1)$ であることは用いてよい。

この問題で使うもの

約数の個数と総和（説明と入口の問題）

この問題を解けるようになるまで（4 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$μ (d)^{2} = 0$ となる約数は和に効かないので、 $n$ の素因数分解を使って、和に残る約数がどんな形をしているかを調べ、両辺を指数 $e_{1}, \dots, e_{r}$ の式で表しましょう。

ヒント 2

$n = p_{1}^{e_{1}} \dots p_{r}^{e_{r}}$ のとき、和に残るのは $p_{1}, \dots, p_{r}$ からいくつかを選んで掛けた約数 $d$ で、そのとき $μ (d)^{2} = 1$ です。また $τ (n^{2}) = \prod (2 e_{i} + 1)$ です。

ヒント 3

$p_{i}$ を選んだ添字の集合を $S$ とすると、 $τ (n / d) = \prod_{i \in S} e_{i} \prod_{i \in / S} (e_{i} + 1)$ となります。これを $S$ について加えた和が、どんな積を展開したものになっているかを考えましょう。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$n = 1$ の場合を確認し、 $n \geq 2$ では素因数分解 $n = \prod p_{i}^{e_{i}}$ から $τ (n^{2}) = \prod (2 e_{i} + 1)$ を求めている（2 点）
$μ (d)^{2} \neq = 0$ となる約数が相異なる素因数の部分集合の積 $d_{S}$ にちょうど対応し、そのとき $μ (d)^{2} = 1$ であることを示している（3 点）
$τ (n / d_{S}) = \prod_{i \in S} e_{i} \prod_{i \in / S} (e_{i} + 1)$ を、指数が $0$ になる素因数の扱いも含めて正しく求めている（2 点）
部分集合 $S$ についての和が積 $\prod_{i} (e_{i} + (e_{i} + 1))$ の展開に一致することを示し、 $τ (n^{2})$ と等しいと結論している（3 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

準備（指数 $0$ を許した約数の個数の公式）. 相異なる素数 $p_{1}, \dots, p_{r}$ と $0$ 以上の整数 $g_{1}, \dots, g_{r}$ に対して
$τ (p_{1}^{g_{1}} \dots p_{r}^{g_{r}}) = (g_{1} + 1) \dots (g_{r} + 1) (1)$
が成り立つ。実際、 $g_{i} = 0$ となる $i$ の因子 $p_{i}^{0} = 1$ を取り除くと、残りは正の指数をもつ相異なる素数のべきの積なので、用いてよい公式が使える（すべての $g_{i}$ が $0$ なら左辺は $τ (1) = 1$ ）。取り除いた $i$ に対する因子は $g_{i} + 1 = 1$ なので、 $(1)$ の右辺の値は変わらない。

場合 1: $n = 1$ . 約数は $d = 1$ のみで、左辺は $μ (1)^{2} τ (1) = 1$ 、右辺は $τ (1) = 1$ なので成り立つ。

場合 2: $n \geq 2$ . $n = p_{1}^{e_{1}} \dots p_{r}^{e_{r}}$ （ $p_{1}, \dots, p_{r}$ は相異なる素数、 $e_{i} \geq 1$ 、 $r \geq 1$ ）と素因数分解する。

ステップ 1（右辺）. $n^{2} = p_{1}^{2 e_{1}} \dots p_{r}^{2 e_{r}}$ なので、 $(1)$ より
$τ (n^{2}) = (2 e_{1} + 1) (2 e_{2} + 1) \dots (2 e_{r} + 1)$
である。

ステップ 2（和に寄与する約数）. $n$ の正の約数 $d$ は、素因数分解の一意性より $d = p_{1}^{c_{1}} \dots p_{r}^{c_{r}}$ （ $0 \leq c_{i} \leq e_{i}$ ）の形にただ 1 通りに書ける。ある $i$ で $c_{i} \geq 2$ なら $d$ は $p_{i}^{2}$ で割り切れるので $μ (d) = 0$ 、したがって $μ (d)^{2} = 0$ で和に寄与しない。すべての $c_{i}$ が $0$ か $1$ のとき、 $d = 1$ なら $μ (d) = 1$ 、そうでなければ $d$ は相異なる素数の積なので $μ (d) = \pm 1$ であり、いずれも $μ (d)^{2} = 1$ である。よって、 ${1, \dots, r}$ の部分集合 $S$ に対して $d_{S} = \prod_{i \in S} p_{i}$ （ $d_{\emptyset} = 1$ ）とおくと、各 $e_{i} \geq 1$ より $d_{S}$ は $n$ の約数であり、異なる $S$ は異なる $d_{S}$ を与えるので
$d ∣ n \sum μ (d)^{2} τ (\frac{n}{d}) = S \subseteq {1, \dots, r} \sum τ (\frac{n}{d _{S}}) (2)$
となる。

ステップ 3（各項の値）. $\frac{n}{d _{S}} = \prod_{i = 1}^{r} p_{i}^{e_{i} - δ_{i}}$ である。ここで $δ_{i}$ は $i \in S$ のとき $1$ 、 $i \in / S$ のとき $0$ で、 $e_{i} \geq 1$ より指数 $e_{i} - δ_{i}$ は $0$ 以上である。 $(1)$ より
$τ (\frac{n}{d _{S}}) = i = 1 \prod r (e_{i} - δ_{i} + 1) = i \in S \prod e_{i} i \in / S \prod (e_{i} + 1)$
となる。

ステップ 4（和の計算）. $r$ 個の因子の積
$i = 1 \prod r (e_{i} + (e_{i} + 1))$
を展開すると、各 $i$ について因子 $e_{i} + (e_{i} + 1)$ から $e_{i}$ と $e_{i} + 1$ のどちらか一方を選んで掛けた項の総和になる。 $e_{i}$ を選ぶ $i$ の集合を $S$ とすると、選び方と部分集合 $S \subseteq {1, \dots, r}$ は 1 対 1 に対応し、その項は $\prod_{i \in S} e_{i} \prod_{i \in / S} (e_{i} + 1)$ である。よって $(2)$ とステップ 3 より
$d ∣ n \sum μ (d)^{2} τ (\frac{n}{d}) = S \sum i \in S \prod e_{i} i \in / S \prod (e_{i} + 1) = i = 1 \prod r (2 e_{i} + 1)$
である。これはステップ 1 より $τ (n^{2})$ に等しい。

結論. 場合 1、2 のどちらでも成り立つので、すべての正の整数 $n$ について
$d ∣ n \sum μ (d)^{2} τ (\frac{n}{d}) = τ (n^{2})$
である。 $■$

（確認: $n = 12 = 2^{2} \cdot 3$ のとき、寄与する約数は $d = 1, 2, 3, 6$ で、 $τ (12) + τ (6) + τ (4) + τ (2) = 6 + 4 + 3 + 2 = 15$ 。一方 $τ (144) = τ (2^{4} \cdot 3^{2}) = 5 \cdot 3 = 15$ で一致する。）

整数論の問題

この問題で使うもの

ヒント

採点の観点と模範解答

次のおすすめ

この問題の確認

間違いを報告する

関連する問題