整数論の問題

数論的関数 $f,g$ のディリクレ積を $(f\ast g)(n)={\sum }_{d\mid n}f(d)g(n/d)$ とし、$1(n)=1$, $\mathrm{id}(n)=n$ とおく。よく知られた関係
$$\tau =1\ast 1,\phi \ast 1=\mathrm{id}\left(\sum _{d\mid n}\phi (d)=n\right),\sigma =\mathrm{id}\ast 1$$
がある（$\sigma (n)$ は $n$ の正の約数の和）。ディリクレ積は結合的なので
$$\phi \ast \tau =\phi \ast (1\ast 1)=(\phi \ast 1)\ast 1=\mathrm{id}\ast 1=\sigma .$$
よって $S=\sigma (360)$。$360=2^3\cdot 3^2\cdot 5$ で $\sigma$ は乗法的だから
$$\sigma (360)=(1+2+4+8)(1+3+9)(1+5)=15\cdot 13\cdot 6=1170.$$

$f(d)=\phi (d)$ と $g(d)=\tau (d)$ はともに乗法的関数なので、そのディリクレ畳み込み $S(n)={\sum }_{d\mid n}\phi (d)\tau (n/d)$ も乗法的である。$360=2^3\cdot 3^2\cdot 5$ より、素数べきごとに計算する。

素数 $p$ と $k\ge 0$ に対し ${\sum }_{j=0}^k\phi (p^j)\tau (p^{k-j})$ を求める（$\phi (1)=1$, $\phi (p^j)=p^j-p^{j-1}$, $\tau (p^m)=m+1$）。

・$2^3$: $j=0$: $1\cdot 4=4$、$j=1$: $1\cdot 3=3$、$j=2$: $2\cdot 2=4$、$j=3$: $4\cdot 1=4$。合計 $15$。
・$3^2$: $j=0$: $1\cdot 3=3$、$j=1$: $2\cdot 2=4$、$j=2$: $6\cdot 1=6$。合計 $13$。
・$5^1$: $j=0$: $1\cdot 2=2$、$j=1$: $4\cdot 1=4$。合計 $6$。

よって $S=15\cdot 13\cdot 6=1170$。

別の確かめ: $\phi \ast \tau =\phi \ast 1\ast 1=\mathrm{id}\ast 1=\sigma$ ではなく、$\phi \ast 1=\mathrm{id}$ なので $\phi \ast \tau =\mathrm{id}\ast 1=\sigma$ である。$\sigma (360)=\sigma (8)\sigma (9)\sigma (5)=15\cdot 13\cdot 6=1170$ で一致する。