定理

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

证明

设 $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)
$$