1. 中国剩余定理（CRT）和 Lagrange 插值的内在联系
-
首先考虑 CRT 是在解决怎样的一个问题：
\[\begin{cases} x&\equiv r_1\pmod{n_1}\\ x&\equiv r_2\pmod{n_2}\\ & \vdots\\ x&\equiv r_m\pmod{n_m}\\ \end{cases} \]其中 \(n_1,\dots,n_m\) 两两互质。求出满足上述同余不等式组的非负整数 \(x\)。
有一种很直观的解决方式，考虑找出这样一组数 \(x_1,\dots,x_m\)，满足：
\[\begin{cases} x_i&\equiv 0\pmod{n_1}\\ x_i&\equiv 0\pmod{n_2}\\ & \vdots\\ x_i&\equiv 1\pmod{n_i}\\ & \vdots\\ x_i&\equiv 0\pmod{n_m}\\ \end{cases} \]那么 \(x=\sum\limits_{i=1}^m r_ix_i\)。
\(x_i\) 的构造方式其实也是容易想到的，记 \(n=\prod\limits_{i=1}^m n_i\)，\(\frac{n}{n_i}\) 模 \(n_i\) 的逆元为 \(y_i\)，然后 \(x_i=n_i y_i\)，且 \(x_i\) 不用对 \(n\) 取模。
-
Lagrange 插值可以通过 \(n\) 个互不相同的点确定一个 \(n-1\) 次多项式 \(f(x)\)。设这 \(n\) 个点分别为 \((x_1,y_1),\dots,(x_m,y_m)\)。
考虑设计 \(f_i(x)\)，满足：
\[\begin{cases} f_i(x_1) &=0\\ f_i(x_2) &=0\\ & \vdots\\ f_i(x_i)&=1\\ & \vdots\\ f_i(x_m)&=0\\ \end{cases} \]那么 \(f(x)=\sum\limits_{i=1}^m y_if_i(x)\)。
\(f_i(x)\) 的构造方式也是容易想到的，\(f_i(x)=\prod\limits_{j=1,j\ne i}^{m}\frac{x-x_j}{x_i-x_j}\)。
这就是 Lagrange 插值公式。
-
考虑这两者之间的联系。首先在需要解决的问题和解决手段上都是类似的，其次考虑改写插值公式：
\[\begin{cases} f(x)&\equiv f(x_1)\pmod{x-x_1}\\ f(x)&\equiv f(x_2)\pmod{x-x_2}\\ & \vdots\\ f(x)&\equiv f(x_m)\pmod{x-x_m}\\ \end{cases} \]Lagrange 插值公式其实就是 CRT 的一种特殊形式。站在问题形式和解决思路的两个角度来看待 Lagrange 插值和 CRT，可以发现它们解法的自然啊。
2. 从 \(\mathbb{Z}_n\) 以及 \(\mathbb{Z}_n^*\) 的性质引出的 \(3\) 个定理
-
考虑群 \(\mathbb{Z}_n=\{0,1,\dots,n-1\}\)，运算定义为模 \(n\) 定义下的加法和乘法。它满足以下性质：
- 加法、乘法都满足封闭性，交换律和结合律。
- 都存在幺元 \(e\)（对于定义在群 \(G\) 上的运算 \(*\)，满足 \(\forall a\in G,a*e=a\) 的 \(e\) 称为 \(*\) 运算的幺元，又称单位元）。其中加法幺元为 \(0\)，乘法幺元为 \(1\)。
- 对于加法，\(\forall a\in \mathbb{Z}_n\) 存在逆元 \(p-a\)；对于乘法，\(\forall a\in \mathbb{Z}_n,(a,n)=1\)，存在逆元，记为 \(a^{-1}\)。
-
Wilson 定理：对于素数 \(p\)，满足 \((p-1)!\equiv-1\pmod{p}\)，这也是 \(p\) 为素数的充要条件。
-
先证明 \(p\) 为素数时满足该条件。考虑 \(\mathbb{Z}_p^*=\{a\in\mathbb{Z}_p^* \mid (a,p)=1\}\)，那么 \(\forall a\in\mathbb{Z}_p^*,a^{-1}\in \mathbb{Z}_p^*\)。由于 \(p\) 是素数，所以 \(\mathbb{Z}_p^*=\mathbb{Z}_p=\{1,2,\dots,p-1\}\)。
由于每个元素都存在逆元，所以可以将一个数和它的的逆元配对。易知不存在 \(a,b\in\mathbb{Z}_p^*,a\ne b\)，满足 \(a^{-1}=b^{-1}\)，故所有元素的逆元互不相同。那么大部分 \(1\sim p-1\) 的数都可以两两配对掉，只有两个逆元等于自己的特例：\(1,p-1\)。
配对后容易得到 \((p-1)!\equiv 1\times (p-1)\equiv -1\pmod{p}\)。
-
再证明该条件是判定 \(p\) 是否为素数的充要条件。上一步已经证明了所有素数 \(p\) 都满足这个条件，也就是必要性，现在只用证明充分性：所有合数都不满足这个条件。
记合数 \(n=p_1^{k_1} p_2^{k_2}\cdots p_m^{k_m}\)，其中 \(p_1,p_2,\dots,p_m\) 互不相同，\(k_1,k_2,\dots,k_m\ge 1\)，该分解是唯一的。
考虑两种情况：
- \(m=1\)。那么将其拆分为 \(n=p_1^{k_1-1}p_1\)，除去特例 \(n=4\)，其余的该形式合数都能找到 \([1,n-1]\) 中的两个不同的数恰好是 \(p_1,p_1^{k_1-1}\) 的倍数。而 \(n=4\) 时，\((n-1)!\equiv 2\pmod 4\)，不满足条件；其余情况 \((n-1)!\equiv 0\pmod {n}\)。
- \(m>1\)。那么 \(p_1^{k_1},p_2^{k_2},\dots,p_m^{k_m}\) 一定是互不相同且 \(\in[1,n-1]\) 的数，所以可以在 \((n-1)!\) 中找到，故 \((n-1)!\equiv 0\pmod {n}\)。
得证。
Wilson 定理就是对 \(\mathbb{Z}_p^*\) 性质的一个简单应用。
-
-
Lagrange 定理：对于群 \(G\)，其子群 \(H\) 必然满足 \(|G|\) 被 \(|H|\) 整除。
-
如何判定子群？一时间容易想到 \(\forall a\in H,ab\in H,a^{-1}\in H\)。这样的话幺元就不需要管了，因为 \(a^{-1}a\in H\)。
但是其实充要条件很简单：\(\forall a,b\in H,ab^{-1}\in H\)。考虑验证：
- 幺元：\(aa^{-1}\in H\)，所以 \(e\in H\)。
- 逆元：\(ea^{-1}\in H\)，所以 \(a^{-1}\in H\)。
- 封闭性：\(a,b^{-1} \in H，a{(b^{-1})}^{-1}\in H\)，所以 \(ab\in H\)。
-
对于一个满足运算封闭性，存在逆元和幺元的群 \(G\)，考虑 \(G\) 的一种特殊的子群 \(H_a\)，表示由 \(a\in G\) 生成的子群，那么 \(H_a=\{e,a^1,a^2,\dots,a^{k-1}\},k=|H_a|\)，由运算的封闭性，\(H_a\subseteq G\)，其中 \(a^k=e\)，\(e,a^1,\dots,a^{i-1}\) 互不相同。
-
如果 \(k=|G|\)，那么自然 \(k\mid |G|\)。
-
如果 \(k<|G|\)，那么必然存在 \(b\notin H,b\in G\)，记 \(bH_a=\{b,ba^1,ba^2,\dots,ba^{k-1}\}\)，那么 \(bH_a\cap H_a=\varnothing\)，因为如果 \(b\notin H,ba^l\in H\)，那么 \((ba^l)(a^l)^{-1}\in H\)，即 \(b\in H\)，矛盾（利用群存在逆元以及运算的封闭性）。
那么只要还存在这样的 \(b\)，一定能找出一组 \(b_1,b_2,\dots,b_m\)，满足 \(b_iH_a=\{b_i,b_ia^1,\dots,b_ia^{k-1}\}\)，且 \(H_a,b_1H_a,b_2H_a,\dots,b_mH_a\) 不交，此时已经不存在 \(b\notin\) 上述子群但是 \(b\in G\) 了，所以 \(H_a\cup b_1H_a\cup b_2H_a\cup \cdots\cup b_mH_a=G\)，而 \(|H_a|=|b_1H_a|=|b_2H_a|=\cdots=|b_mH_a|=k\)，所以 \(k(m+1)=|G|\)，故 \(k=|H|\) 整除于 \(|G|\)。
其实这样的 \(bH=\{bh\in H\mid h\in H\}\) 称为 \(H\) 的左陪集，\(Hb=\{hb\in H\mid h\in H\}\) 称为 \(H\) 的右陪集，上述通过特殊的子群 \(H\) 说明 Lagrange 定理的方式其实是在对 \(G\) 做陪集分解。
-
-
考虑推广，其实任何子群 \(H\subseteq G\) 都满足这个性质，因为在分解过程中，我们发现只需要保证 \(H,G\) 都存在逆元，且运算满足封闭性，而这些群基本性质都是在 \(G\) 的定义中保证了。所以我们用一种通俗的陪集分解方式粗糙地证明了 Lagrange 定理。
-
-
Euler 定理：对于 \((a,n)=1,a^{\varphi(n)}\equiv 1\pmod{n}\)。
考虑 \(3\) 里面的 \(H_a\)，对于 \(a\in G\)，最小的满足 \(a^k=e\) 的 \(k\) 称为 \(a\) 的阶，也是 \(H_a\) 的阶。那么 Lagrange 定理就有另一种描述方式：考虑群 \(G\)，任意子群 \(H\subseteq G\) 的阶都是 \(G\) 的阶的因子。
考虑群 \(\mathbb{Z}_n^*\)，所有与 \(n\) 互质且介于 \([1,n-1]\) 的数 \(a\) 都在 \(\mathbb{Z}_n^*\) 中。故 \(|\mathbb{Z}_n^*|=\varphi(n)\)。考虑 \(a\in\mathbb{Z}_n^*\)，那么 \(a\) 的阶 \(k\) 应该满足 \(a^k=e\)，而在 \(\mathbb{Z}_n^*\) 中 \(e=1\)，运算就是模 \(n\) 意义下的乘法，所以 \(a^k\equiv1 \pmod{n}\)。而 \(\forall a\in \mathbb{Z}_n^*\) 的 \(a\) 的阶都是 \(\mathbb{Z}_n^*\) 的阶的因子，所以 \(k\mid \varphi(n)\) ，那么自然 \(a^{\varphi(n)}=a^{kl}=e^l=e\)，即 \(a^{\varphi(n)}\equiv 1\pmod{n}\)。而由于 \(a\in\mathbb{Z}_n^*\)，所以 \(a\) 的限制就是 \((a,n)=1\)。Euler 定理得证。
当 \(n=p\) 为质数时就是 Euler 定理的一种特殊形式，Fermat 小定理：\(a^{p-1}\equiv 1\pmod {p}\)，其中 \(p\) 为质数。
是不是说 Lagrange 定理 \(>\) Euler 定理 \(>\) Fermat 小定理。因为 Euler 定理可以理解为 Lagrange 定理为取 \(G=\mathbb{Z}_n^*\) 的一种特殊形式，而 Fermat 小定理是 Lagrange 定理为取 \(G=\mathbb{Z}_p^*\) 的一种特殊形式，也是 Euler 定理取 \(n=p\) 的特殊形式。从中可以看出 Lagrange 定理的强大！
3. 由循环群引申出的一系列问题
-
循环群的引入：在证明 Lagrange 定理时，用到了一个特殊的子群 \(\{e,a,a^2,a^3,\dots,a^{k-1}\}\) 这个 \(k\) 元群。\(a^k=e\)，这就是一个循环群。
定义：对于群 \(\{G,\cdot\}\)，如果对于任意子群 \(H_g=\{g^k\mid g\in G\}\) 都满足 \(H_g\) 其实就是 \(G\) 的一个循环移位后的结果，那么 \(\{G,\cdot\}\) 就是一个循环群。
将大小为 \(k\) 的循环群称作 \(k\) 阶循环群。有一些常见的循环群，如 \(\{\mathbb{Z}_n,+,\times\}\)，\(\{\{-1,1\},\times\}\)，\(k\) 次单位根 \(\{\{1,{\omega}_k,{\omega}_k^2,\dots,{\omega}_k^{k-1}\},\times\}\)。
受到单位根的启发，容易想到将 \(k\) 阶循环群看作一个正 \(k\) 边形。实际上，取一个单位圆，将其等分为 \(k\) 份，将这 \(k\) 个顶点作为 \(k\) 阶循环群的 \(k\) 个元素，连起来就是代表该循环群的正 \(k\) 边形。
-
作用在循环群上面的变换：\(k\) 阶循环群共有 \(k\) 种旋转方式使得最后对应的多边形仍然能重合。当我们在旋转的时候，可以看作 \(k\) 个元素的循环轮换，由 \((x_1,x_2,\dots,x_n)\) 变成 \((x_2,\dots,x_n,x_1)\)，再是 \((x_3,\dots,x_n,x_1,x_2)\)……最后是 \((x_n,x_1,\dots,x_{n-1})\)。
当然，如果我们以该 \(k\) 边形从顶点引出的 \(k\) 条对称轴来看的话，这又是关于这 \(k\) 条对称轴的一次轮换了。
-
一个具体的问题，假设这里有一个立方体，有多少种互异的旋转方案可以使得该立方体在旋转后和旋转前完全重合呢？
-
不旋转，\(1\) 种。
-
旋转轴为正方形的体对角线，也就是红色虚线。旋转 \(120\degree,240\degree\) 都是可行的。一共有 \(4\) 条体对角线，这就是 \(4\times 2=8\) 种。
-
旋转轴为正方形的对面中心连线，也就是紫绿色射线。旋转 \(90\degree,180\degree,270\degree\) 都是可行的。一共有 \(3\) 条对面中心连线，\(3\times3=9\) 种。
-
在斜截面上，且过斜对的两条棱的重点。旋转 \(180\degree\) 是可行的。\(6\times1=6\) 种。
共 \(1+8+9+6=24\) 种变换。如果将不旋转看作单位元，这相当于是一种群作用。将变换作用在立方体上。
但不觉得这个 \(24\) 很神秘吗？将 \(4\) 条体对角线看作一个 \(4\) 阶循环群，这 \(24\) 种变换相当于遍历了这个 \(4\) 阶循环群的 \(4!=24\) 种排列。手玩容易证明这是构成一一对应的。也就是说，一组群作用对应了一个循环群，是不是很神奇！
-
-
将群看作一种作用在集合上的变换。对于群 \(G\)，考虑 \(a,b,\in G, b\ne e\)，那么 \(ab\) 一定对应了一个新的元素。考虑将 \(a\to ab\) 连有向边，容易发现，这应该会连出来一个大小为 \(|G|\) 的完全图。
考虑一种群作用：找出 \(x_1,x_2\in G\)，使得 \(x_1x_2=e\)，这是一种特殊情况。不写了摆了。
4. 群和数论函数的关联
-
数论函数的另一种理解方式：数论函数本身是一种映射 \(f:\mathbb{N}\to \mathbb{R}\)（从 \(0\) 开始）；或者 \(f:\mathbb{N^*}\to \mathbb{R}\)（从 \(1\) 开始）。考虑将这种映射 \(f\) 看成一个数列 \(a\)，\(a_i=f(i)\)。也就是说可以将数论函数看作数列。
将数论函数 \(f\) 映射成无穷数列 \(\{a\}\)。
考虑一些数论函数之间的乘法，\(h(x)=f(x)g(x)\)，用数列表示就是 \(c_n=a_nb_n\)，这是最简单的点乘。
考虑一些更有意思的乘法，这时候（满足 \(f:\mathbb{N}\to \mathbb{R}\)）考虑 \(c_n=\sum\limits_{i=0}^n a_ib_{n-i}\)。这其实是一种基于加法定义的“卷积”。感觉这个形式很眼熟啊，记 \(A(x)=a_0+a_1x+a_2x^2+\cdots\)，那么 \(c_n\) 就是 \(A(x)B(x)\) 的 \(n\) 次项系数。这不就是多项式乘法吗？不过在这里，\(A(x)\) 是一个无限长的多项式，我们称之为形式幂级数，或者说，生成函数（Generating Function）。
梳理一下，我们可以将一个数论函数 \(f:\mathbb{N}\to \mathbb{R}\) 映射到一个无穷数列 \(\{a\}\) 上，将这个无穷数列的第 \(i\) 项看成 \(i\) 次项系数，构造一个形式幂级数 \(A(x)\)。这三者都是一一对应关系。
-
形式幂级数的应用：考虑一些特定的数论函数对应的形式幂级数的性质。
-
等比数列：比如 \(f(n)=2^n\to a_n=2^n \to A(x)=\sum\limits_{i=0}^{\infty} 2^ix^i\)。看到这个等比数列很容易想起来一个初中数学常用公式，\(1+2+2^2+\cdots+2^n=2^{n+1}-1\)，那么我们的 \(A(x)\) 是否也存在一个这样的表示呢？
考虑上述定义的多项式乘法，\(A(x)B(x)=C(x)\)，如果我们取 \(B(x)=1-2x\)，那么容易得到 \(C(x)=1\)。画一下就明白了。此时 \(C(x)\) 对应数列 \(c_0=1,c_1=0,c_2=0,\dots,c_n=0,\dots\)，我们发现任何一个 \(A(x)\) 乘上 \(C(x)\) 得到的还是 \(A(x)\) 本身，所以说 \(C(x)\) 相当于一个幺元的存在。这么说，这里的 \(B(x)=1-2x\) 就是 \(A(x)=\sum\limits_{i=0}^{\infty} 2^ix^i\) 的“逆”咯。这是多项式的逆。
-
Finonacci 数列：\(f_0=1,f_1=1,f_2=2,f_3=3,f_4=5,\dots,f_n=f_{n-2}+f_{n-1},\dots\)，大家都知道 Fibonacci 数列的生成函数 \(F(x)=\frac{1}{1-x-x^2}\)，试着用另一种角度来理解它。
考虑 \(A(x)=\sum\limits_{i=0}^{\infty}f_ix^i,B(x)=1-x-x^2\)，那么容易发现 \(A(x)B(x)=1\)。也就是说 \(B(x)\) 是 \(A(x)\) 的逆。其实这个很好推，我们观察一下什么样的幂级数 \(A(x)\) 会拥有逆。
- \(a_0b_0=1,a_0\ne 0\)。
- \(\forall n>0,\sum\limits_{i=0}^n a_ib_{n-i}=0\)。
考虑如果 \(a\) 已知，且满足第一个条件，是否能通过条件 \(2\) 得出确定的 \(b\)？
\[a_0{\color{red}{b_1}}+a_1b_0=0\\ a_0{\color{red}{b_2}}+a_1b_1+a_2b_0=0\\ a_0{\color{red}{b_3}}+a_1b_2+a_2b_1+a_3b_0=0\\ \dots \]从上至下处理每个限制，每一行标红的是处理到这个限制时还未知的系数。发现顺次解决下来，每一行都是一个一元一次方程。所以可以解出 \(B(x)\) 的全部系数。也就是说，如果保证 \(a_0\ne 1\)，令 \(a_0b_0=1\)，可以求出一个 \(B(x)\) 满足 \(A(x)B(x)=1\)，即 \(B(x)\) 为 \(A(x)\) 的逆。
再来想一件事，满足 \(a_n=2a_{n-1}\) 的递推数列 \(a\) 对应的 \(A(x)\) 的逆 \(B(x)=1-2x\) 是一个 \(1\) 次多项式；满足 \(a_{n}=a_{n-2}+a_{n-1}\) 的递推数列 \(a\) 对应的 \(A(x)\) 的逆 \(B(x)=1-x-x^2\) 是一个 \(2\) 次多项式。
容易猜到一个结论：假如数列 \(a\) 的递推式为 \(a_n=\sum\limits_{i=n-k}^{n-1} h_i a_i\)，也就是说 \(a_n\) 的值和它前面的 \(k\) 项有关时，\(a\) 对应的的生成函数 \(A(x)\) 的逆 \(B(x)\) 是一个 \(k\) 次多项式。想一想有点显然，不证了，具体就是解方程。
-
-
Dirichlet 卷积与 Möbius 反演：刚才讲的卷积（多项式乘法）是根据系数的加法定义的（\(c_n=\sum\limits_{i=0}^n a_ib_{n-i}\)），现在考虑用系数的乘法来定义一种卷积。既然涉及到乘法，那么就不考虑 \(a_0\) 了，于是这次的映射是 \(f:\mathbb{N^*}\to \mathbb{R}\) 的。定义 Dirichlet 卷积 \(*\)：\(h=f*g\)，则 \(h_n=\sum\limits_{d\mid n}f_{d}g_{\frac{n}{d}}\)。这种运算显然满足交换律，结合律，存在逆元和单位元 \(1\)，是一种合法的群运算（映射）。
现对于一个数列 \(f\)，考虑数列 \(g_n=1\)，\(h=f*g\)。那么此时仍然考虑求逆，\(f=h*t\)，求 \(t\)。先回代，\(h=(h*t)*g\)，由结合律 \(h=h*(t*g)\)，所以 \(t*g=e\)。再次归到生成函数上面解决吧，相当于求出 \(g\) 的逆。
\((1+x+x^2+\cdots)*T(x)=1\)，那么考虑将 Dirichlet 卷积对应的系数关系展开：
\[t_1=1\\ t_1+t_2=0\\ t_1+t_3=0\\ t_1+t_2+t_4=0\\ t_1+t_5=0\\ t_1+t_2+t_3+t_6=0\\ \dots \]解一下：
\[t_1=1\\ t_2=-1,t_3=-1\\ t_4=0\\ t_5=-1\\ t_6=1\\ \dots \]其实就是 \(\forall n>1,\sum\limits_{d\mid n}t_d=0\)。试着归纳地解一下 \(t\)。
首先 \(t_1=1\)，这是边界。
- \(n\) 是质数。那么 \(t_1+t_n=0\)，故 \(t_n=-1\)。
- \(n\) 由两个质因数 \(p,q\) 组成。那么 \(t_1+t_{p}+t_{q}+t_{pq}=0\)，那么 \(t_n=t_{pq}=1\)。
- \(n\) 由三个质因数 \(p_1,p_2,p_3\) 组成。那么 \(t_1+t_{p_1}+t_{p_2}+t_{p_3}+t_{p_1p_2}+t_{p_1p_3}+t_{p_2p_3}+t_{p_1p_2p_3}=0\)，那么 \(t_n=t_{p_1p_2p_3}=-1\)。
- 由是可以归纳了，假如 \(n\) 由 \(k\) 个质因子 \(p_1,p_2,\dots,p_k\) 组成，那么从这 \(k\) 个质因子中选 \(0\) 个组成的数在等式左侧贡献为 \(\binom{k}{0}\)，选 \(1\) 个的贡献为 \(-\binom{k}{1}\)，选 \(2\) 个的贡献为 \(\binom{k}{2}\)……，最后，\(t_n=t_{p_1\cdots p_k}=-\binom{k}{0}+\binom{k}{1}-\binom{k}{2}+\binom{k}{3}-\cdots\)，有一些组合数基础可以发现最终算出的 \(t_n=(-1)^k\)。
也就是说，如果 \(n\) 没有平方因子，可以恰好表示为 \(k\) 个互不相同素数的乘积 \(n=p_1p_2\cdots p_k\)，那么 \(t_n=(-1)^k\)。接下来考虑 \(n\) 有平方因子的情况。
- \(n=p^2\)。那么 \(t_1+t_p+t_{p^2}=0\)，故 \(t_n=t_{p^2}=0\)。
- \(n=p^3\)，那么 \(t_1+t_p+t_{p^2}+t_{p^3}=0\)，故 \(t_n=t_{p^3}=0\)。容易发现对于 \(n=p^k\)，\(t_n=t_{p^k}=0\)。
- 假如对于原先的 \(n=p^2\)，多了一个不同于 \(p\) 的质因子 \(q\)，那么相较于 \(t_1+t_p+t_{p^2}=0\)，左侧多了 \(t_{q}+t_{pq}+t_{p^2q}\)，由于 \(t_q+t_{pq}=0\)，所以 \(t_{p^2q}=0\)。
于是可以归纳得到对于含有平方因子的 \(n\)，有 \(t_n=0\)。
综上，\(t_n\begin{cases} 1 & n=1 \\ (-1)^k & n=p_1p_2\cdots p_k \\ 0 & \exist p,p^2\mid n\end{cases}\)
我们称这个 \(t\) 为 Möbius 函数 \(\mu\)，容易发现这个 \(\mu\) 是积性函数（满足 \(\forall a,b,(a,b)=1,\mu(a)\mu(b)=\mu(ab)\)），如果 \(f,g\) 都是积性函数，那么 \(f*g\) 也是积性函数。
上述过程其实是 Möbius 反演公式的推导：
\[h=f*g \Leftrightarrow f=\mu * h,其中 \forall i,g_i=1 \]或者说，
\[h(n)=\sum\limits_{d\mid n} f(d) \Leftrightarrow f=\sum\limits_{d\mid n} h(d)\mu(\frac{n}{d}) \]