数学/数论专题：莫比乌斯函数与欧拉函数（进阶）
0. 前言1. 前置知识2. 正文3. 总结4. 参考资料0. 前言
本篇文章会从狄利克雷卷积的角度，讨论莫比乌斯函数与欧拉函数的相关性质。
或者说就是利用狄利克雷卷积重新证一遍这两个函数的性质以及弄出几个新的式子。
其实我觉得这块还是挺妙的，也可能是我做 DP 和数据结构做疯了（
1. 前置知识
首先您需要知道欧拉函数，狄利克雷卷积，莫比乌斯函数+莫比乌斯反演。
如果不知道，可以搜索别人的博文或者前往我的博文进行学习：
数学/数论专题-学习笔记：欧拉函数数学/数论专题-学习笔记：狄利克雷卷积数学/数论专题-学习笔记：莫比乌斯反演
接下来是一些必要的前置知识与性质，有些前面的博文有但是我会再提一遍。
[A][A][A] 表示 AAA 为真时值为 1，否则为 0。
五类数论函数：
单位（元）函数/元函数 ϵ(n)=[n=1]\epsilon(n)=[n=1]ϵ(n)=[n=1]。常数函数 I(n)=1I(n)=1I(n)=1，或者记作 1(n)=11(n)=11(n)=1。恒等函数 id(n)=nid(n)=nid(n)=n。欧拉函数 φ(n)=∑i=1n[gcd(i,n)=1]\varphi(n)=\sum_{i=1}^{n}[\gcd(i,n)=1]φ(n)=∑i=1n[gcd(i,n)=1]莫比乌斯函数 μ(n)\mu(n)μ(n)。
两个基础定义：
积性函数：对于数论函数 f(n)f(n)f(n)，若 gcd(i,j)=1\gcd(i,j)=1gcd(i,j)=1 时有 f(ij)=f(i)f(j)f(ij)=f(i)f(j)f(ij)=f(i)f(j)，则 f(n)f(n)f(n) 是积性函数。特别的，若 gcd(i,j)≠1\gcd(i,j) \ne 1gcd(i,j)=1 时仍有 f(ij)=f(i)f(j)f(ij)=f(i)f(j)f(ij)=f(i)f(j)，那么 f(n)f(n)f(n) 是完全积性函数。逆元：对所有 f(1)≠0f(1) \ne 0f(1)=0 的函数，如果 f∗g=ϵf*g=\epsilonf∗g=ϵ，那么 ggg 是 fff 的逆元，记作 f−1f^{-1}f−1。
一个基础性质：
设 f(n),g(n)f(n),g(n)f(n),g(n) 是积性函数，则 f∗gf*gf∗g 还是积性函数。对任意数论函数 f(n)f(n)f(n)，f∗ϵ=ff*\epsilon=ff∗ϵ=f
2. 正文
先看莫比乌斯函数。
首先，莫比乌斯函数有个性质，就是 I∗μ=ϵI*\mu=\epsilonI∗μ=ϵ，即 μ=I−1\mu=I^{-1}μ=I−1。
然后令 g=I∗fg=I*fg=I∗f，根据 f=f∗ϵ=f∗I∗μ=g∗μf=f*\epsilon=f*I*\mu=g*\muf=f∗ϵ=f∗I∗μ=g∗μ 我们就得到了莫比乌斯反演的式子。
从狄利克雷卷积角度，很容易证明 ∑d∣nμ(d)=[n=1]\sum_{d \mid n}\mu(d)=[n=1]∑d∣nμ(d)=[n=1]，因为 I∗μ=ϵI*\mu=\epsilonI∗μ=ϵ 展开就是这个式子。
对于另一个莫比乌斯反演的式子，就是新定义 t=f⊕gt=f\oplus gt=f⊕g 为 t(i)=∑i∣nf(n)g(ni)t(i)=\sum_{i \mid n}f(n)g(\dfrac{n}{i})t(i)=∑i∣nf(n)g(in) 然后推式子。
然后就没什么新鲜的性质了。
然后是欧拉函数。
证明一个性质：φ∗I=id\varphi*I=idφ∗I=id，即 ∑d∣nφ(d)=n\sum_{d \mid n}\varphi(d)=n∑d∣nφ(d)=n。
首先因为 φ,I\varphi,Iφ,I 都是积性函数，故 φ∗I\varphi*Iφ∗I 还是积性函数，因此只需要证明 (φ∗I)(pk)=pk(\varphi*I)(p^k)=p^k(φ∗I)(pk)=pk 即可，其中 ppp 是质数，k≥1k \geq 1k≥1。
这玩意的证明就是根据 φ(pk)=pk−pk−1\varphi(p^k)=p^k-p^{k-1}φ(pk)=pk−pk−1，然后将这个 (φ∗I)(pk)(\varphi*I)(p^k)(φ∗I)(pk) 展开就可证明了。
狄利克雷卷积的优势就在于证明积性函数这一步直接就证完了，没必要暴力展开。
根据这几点开始搞事情，我们发现莫反的展开式与上面欧拉函数的性质展开式貌似很像。
g(n)=∑d∣nf(d)⇒f(n)=∑d∣ng(d)μ(nd),n=∑d∣nφ(n)g(n)=\sum_{d \mid n}f(d)\Rightarrow f(n)=\sum_{d \mid n}g(d)\mu(\dfrac{n}{d}),n=\sum_{d \mid n}\varphi(n)g(n)=∑d∣nf(d)⇒f(n)=∑d∣ng(d)μ(dn),n=∑d∣nφ(n)。
因此如果将 ggg 替换成 ididid，将 fff 替换成 φ\varphiφ，我们发现上述式子依然成立，因为 id=I∗φid=I*\varphiid=I∗φ，然后带入莫反式可得 φ=id∗μ\varphi=id*\muφ=id∗μ，这就是 φ\varphiφ 与 μ\muμ 的关系。
展开一下得到：
φ(n)=∑d∣ndμ(nd)\varphi(n)=\sum_{d \mid n}d\mu(\dfrac{n}{d})φ(n)=d∣n∑dμ(dn)
另外，变一下得到 φ(n)=∑d∣nndμ(d)\varphi(n)=\sum_{d \mid n}\dfrac{n}{d}\mu(d)φ(n)=∑d∣ndnμ(d)，然后两边同时除以 nnn，得到：
φ(n)n=∑d∣nμ(d)d\dfrac{\varphi(n)}{n}=\sum_{d \mid n}\dfrac{\mu(d)}{d}nφ(n)=d∣n∑dμ(d)
这两个式子可以将 μ\muμ 与 φ\varphiφ 互相转化（当然可以直接 φ=id∗μ\varphi=id*\muφ=id∗μ），顺便消去一个求和符号。
3. 总结
本篇文章从狄利克雷卷积的角度，推理了各种性质，最后得到了 φ=id∗μ\varphi=id*\muφ=id∗μ 也就是 φ(n)n=∑d∣nμ(d)d\dfrac{\varphi(n)}{n}=\sum_{d \mid n}\dfrac{\mu(d)}{d}nφ(n)=∑d∣ndμ(d)。
