欧拉反_

欧拉反演

前言：因为一直记错这个东西，所以来写一下。

欧拉反演

$$\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$

---

参考文献：

[1] https://www.cnblogs.com/Morning-Glory/p/11106828.html