OMC182(F)

　乗法的関数に関する知識がなくても、以下のようにして解くことができる。 　 $n={p_1}^{q_1}{p_2}^{q_2}\cdots {p_m}^{q_m}$ において， $\mathrm{gcd}(k,n)=\mathrm{gcd}(k,{p_1}^{q_1})\mathrm{gcd}(k,{p_2}^{q_2})\cdots \mathrm{gcd}(k,{p_m}^{q_m})$ である．また，中国剰余定理より， $1$ 以上 $n$ 以下の整数 $i$ は，以下を満たす $m$ 個の整数の組と一対一対応できる．$$A_i=({a_i}_{1},{a_i}_{2},\cdots,{a_i}_{m})(0\leq a_j \leq {p_{j-1}}^{q_{j-1}},i \equiv {a_i}_s \pmod {{p_s}^{q_s}})$$ 　ここで， $\mathrm{gcd}(k,{p_s}^{q_s})=\mathrm{gcd}(k \pmod {{p_s}^{q_s}},{p_s}^{q_s})=\mathrm{gcd}({a_k}_s,{p_s}^{q_s})$ となるので，

$\mathrm{gcd}(k,n)=\mathrm{gcd}({a_k}_1,{p_1}^{q_1})\mathrm{gcd}({a_k}_2,{p_2}^{q_2})\cdots \mathrm{gcd}({a_k}_m,{p_m}^{q_m})$ と書き換えられる．よって， に， $0$ 以上 ${p_s}^{q_s}$ 以下の数が全て同じ回数現れることより，

$f(n)=\sum\limits_{k=1}^{n} \mathrm{gcd}(k,n)$

$= (\mathrm{gcd}(0,{p_1}^{q_1})+\mathrm{gcd}(1,{p_1}^{q_1})+\cdots +\mathrm{gcd}({p_1}^{q_1}-1,{p_1}^{q_1})) \cdots (\mathrm{gcd}(0,{p_m}^{q_m})+\mathrm{gcd}(1,{p_m}^{q_m})+\cdots +\mathrm{gcd}({p_m}^{q_m}-1,{p_m}^{q_m}))$

$=\prod\limits_{x=1}^{m} ((q_x+1)p_x-q_x){p_x}^{q_x-1}$ となり，

これは本解説の $\prod\limits_{p|n} p^{\mathrm{ord}_p (n)-1}((p-1)\mathrm{ord}_p (n) +p)$ と同値である．