就是证明，用狄利克雷卷积做，欧拉反演狗都不用/oh
\(\sum\limits_{d|n}\varphi(d) = n\)。
长得很像狄利克雷卷积，令 \(g(n)\) 恒等于 \(1\)，作 \(\varphi(n)\) 与 \(g(n)\) 的狄利克雷卷积。
\((f*g)(n) = \sum\limits_{d|n}\varphi(d)\)。
好没用的卷积。
然后怎么做呢？注意到 \(f, g\) 都是积性函数，则 \(f*g\) 也是积性函数。我们可以考虑证明一些关于 \(n\) 为质数的结论然后乘起来。
对于 \(n\) 为质数原命题显然成立。
对于 \(n\) 为质数整数次幂，设 \(n = p^m = \prod\limits_{i = 1}^m p\)（\(p\) 为质数，\(m\) 为正数），则 \((f*g)(n) = \prod\limits_{i = 1}^m (f*g)(p) = \prod\limits_{i = 1}^m (f*g)(p) = \prod\limits_{i = 1}^m p = p^m\)。
对于 \(n\) 为任意整数，设 \(n\) 唯一分解后为 \(p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}\)，则 \((f*g)(n) = \prod\limits_{i = 1}^k (f*g)(p_i^{c_i}) = \prod\limits_{i = 1}^k p_i^{c_i} = n\)。
原命题得证。
其实知道质数成立，然后是积性函数，其实就证明出来了。
所以你看，这是很简单的。
标签：limits,卷积,质数,varphi,证明,反演,积性,prod,欧拉 From： https://www.cnblogs.com/thirty-two/p/16640604.html