欧拉反演
前言：因为一直记错这个东西，所以来写一下。
欧拉反演 \[ \mathrm{id}=\varphi * \mathbf{1}\Longleftrightarrow n=\sum_{d \mid n} \varphi(d) \] 其中 \(*\) 是狄利克雷卷积。参考 生成函数 学习笔记 。
例：证明下式 \[ \sum_{i=1}^n \gcd(i, n)=\sum_{d \mid n} \frac{n}{d} \varphi(d) \]
证明 根据引理有 \[ \gcd(i,j) = \sum_{d \mid \gcd(i,j)}\varphi(d) = \sum_{d\mid i}\sum_{d \mid j} \varphi(d) \] 那么 \[ \begin{aligned} \sum_{i=1}^n \gcd(i, n) &= \sum_{i=1}^n\sum_{d\mid i}\sum_{d \mid n} \varphi(d) \\[6pt] &=\sum_{d \mid n} \sum_{i=1}^n\sum_{d\mid i} \varphi(d) \\[6pt] &= \sum_{d \mid n}\frac{n}{d}\varphi(d) \end{aligned} \]
\(\square\)
参考文献：
