定理

$$
\sum_{\gcd(d,n)=1}\gcd(d-1,n)=\sigma_0(n) \cdot \phi(n)
$$

证明

A062355

设 $S=\{0,1,2,\cdots,n-1\}$

构造 $\phi(n)$ 个映射,即 $\forall \gcd(\gamma,n)=1$,有映射 $f_{\gamma}(y)=(\gamma \cdot y)\bmod n$,显然它是一个满射且是单射,于是它是一个双射,也就构成置换

考虑 $y_1,y_2$ 处于一个轨道中的情况:$\exists \gcd(\gamma,n)=1,f_{\gamma}(y_1) \equiv y_2 \pmod {n}$

即:$\gamma \cdot y_1 \equiv y_2 \pmod {n}$

于是 $y_1,y_2$ 在一个轨道的条件是 $\gcd(n,y_1)=\gcd(n,y_2)$

于是就一共有 $\sigma_0(n)$ 个轨道

burnside 引理 可以得知:

$$
\begin{split}
|X/G|&=\frac 1{|G|}\sum_{g\in G}|x^g| \\
等价类个数&=不动元个数的平均数
\end{split}
$$

在置换 $f_{\gamma}$ 下,不动点为 $\gamma \cdot x \equiv x \pmod{n}$,即 $(\gamma - 1)x \equiv 0 \pmod {n}$,一共有 $\frac{n}{\gcd(\gamma - 1, n)}$ 个

即:

$$
\phi(n)=\frac{1}{\sigma_0(n)}\sum_{\gcd(d,n)=1} \gcd(d - 1,n)
$$

即:

$$
\sum_{\gcd(d,n)=1}\gcd(d-1,n)=\phi(n) \cdot \sigma_0(n)
$$