整数論の問題

一般の正の整数 $n$ について $S(n)=\sum _{\begin{array}{c}1\leqq k\leqq n\\ \gcd (k,n)=1\end{array}}\gcd (k-1,n)$ を求める。$\phi$ をオイラー関数、$\tau (n)$ を $n$ の正の約数の個数とする。

ガウスの公式の利用: 正の整数 $m$ について $\sum _{d\mid m}\phi (d)=m$ が成り立つ。これを $m=\gcd (k-1,n)$ に用いると（$\gcd (0,n)=n$ の場合も含めて）$$\gcd (k-1,n)=\sum _{d\mid \gcd (k-1,n)}\phi (d)=\sum _{\begin{array}{c}d\mid n\\ d\mid k-1\end{array}}\phi (d).$$

和の順序交換: $$S(n)=\sum _{d\mid n}\phi (d)\cdot A_d,A_d=\#\{k:1\leqq k\leqq n,\gcd (k,n)=1,k\equiv 1(\mathrm{mod}d)\}.$$

$A_d$ の計算: $d\mid n$ のとき、還元写像 $\pi :(\mathbb{Z}/n\mathbb{Z}{)}^{\times }\to (\mathbb{Z}/d\mathbb{Z}{)}^{\times }$、$k\mathrm{mod}n\mapsto k\mathrm{mod}d$ は群の準同型である。これは全射である：$n=\prod p^{e_p}$、$d=\prod p^{f_p}$（$f_p\leqq e_p$）とし、$\gcd (a,d)=1$ となる $a$ に対して、中国剰余定理で $k\equiv a(\mathrm{mod}{p}^{e_p})$（$f_p\geqq 1$ の $p$）、$k\equiv 1(\mathrm{mod}{p}^{e_p})$（$f_p=0$ の $p$）となる $k$ をとれば、$k$ は $n$ と互いに素で $k\equiv a(\mathrm{mod}d)$ となる。$A_d$ は $\pi$ の核の位数なので $$A_d=\frac{|(\mathbb{Z}/n\mathbb{Z}{)}^{\times }|}{|(\mathbb{Z}/d\mathbb{Z}{)}^{\times }|}=\frac{\phi (n)}{\phi (d)}.$$

結論: $$S(n)=\sum _{d\mid n}\phi (d)\cdot \frac{\phi (n)}{\phi (d)}=\phi (n)\sum _{d\mid n}1=\phi (n)\tau (n).$$

$n=360=2^3\cdot 3^2\cdot 5$ について
$$\phi (360)=360\cdot \frac{1}{2}\cdot \frac{2}{3}\cdot \frac{4}{5}=96,\tau (360)=(3+1)(2+1)(1+1)=24.$$
よって $$S=96\cdot 24=2304.$$

（小さい例で確認: $n=4$ では $k=1,3$ で $\gcd (0,4)+\gcd (2,4)=4+2=6=\phi (4)\tau (4)=2\cdot 3$。）

メノンの恒等式 ${\sum }_{\gcd (k,n)=1}\gcd (k-1,n)=\phi (n)\tau (n)$ を使う（$k=1$ の項は $\gcd (0,n)=n$）。

$360=2^3\cdot 3^2\cdot 5$ なので $\phi (360)=360\cdot \frac{1}{2}\cdot \frac{2}{3}\cdot \frac{4}{5}=96$、$\tau (360)=4\cdot 3\cdot 2=24$。よって $S=96\cdot 24=2304$。

恒等式の確認（乗法性）: $S(n)={\sum }_{d\mid n}d\phi (n/d)\cdot \#\{\dots \}$ の形に帰着でき、$S$ は乗法的。素数べき $p^a$ では $S(p^a)=\phi (p^a)(a+1)$ となる。例として $n=2$ では $k=1$ のみで $\gcd (0,2)=2=\phi (2)\tau (2)$、$n=3$ では $k=1,2$ で $3+1=4=2\cdot 2$ と一致。
$p=2,a=3$: $4\cdot 4=16$、$p=3,a=2$: $6\cdot 3=18$、$p=5$: $4\cdot 2=8$。積 $16\cdot 18\cdot 8=2304$。