• $\epsilon = \mu * 1$，证明：二项式定理$(1 - 1)^2 = 0$。
• $\operatorname{id} = \varphi * 1$，证明：真分数约分。
• $\varphi= \mu * \operatorname{id}$，证明：上面式子左右卷$\mu$。

求 $$\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)$$ 先枚举$d = \gcd(i,j)$，再套用$\epsilon = \mu * 1$ $$=\sum_{d=1}^{n}d\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}[\gcd(i,j)=1]$$ $$=\sum_{d=1}^{n}d\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}\sum_{p|\gcd(i,j)}\mu(p)$$ 再枚举$p$ $$=\sum_{d=1}^{n}d\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(p)\sum_{i=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{dp} \right\rfloor}1$$ $$=\sum_{d=1}^{n}d\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(p)\frac{\left\lfloor \frac{n}{dp} \right\rfloor(\left\lfloor \frac{n}{dp} \right\rfloor + 1)\left\lfloor \frac{m}{dp} \right\rfloor(\left\lfloor \frac{m}{dp} \right\rfloor + 1)}{4}$$ 设$T=dp$，枚举$T$ $$=\sum_{T=1}^{n} \frac{\left\lfloor \frac{n}{T} \right\rfloor(\left\lfloor \frac{n}{T} \right\rfloor + 1)\left\lfloor \frac{m}{T} \right\rfloor(\left\lfloor \frac{m}{T} \right\rfloor + 1)}{4}\sum_{d|T}d\mu(\frac{T}{d})$$ 套用$\varphi= \mu * \operatorname{id}$ $$=\sum_{T=1}^{n} \frac{\left\lfloor \frac{n}{T} \right\rfloor(\left\lfloor \frac{n}{T} \right\rfloor + 1)\left\lfloor \frac{m}{T} \right\rfloor(\left\lfloor \frac{m}{T} \right\rfloor + 1)}{4}\varphi(T)$$ 求出欧拉函数前缀和，直接整除分块即可。

上述过程中最为关键的是设$T=dp$，枚举$T$这一步。该操作可以概括为如下等式：$$\sum_{d=1}^{n}f(d)\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}g(p)h(dp)=\sum_{T=1}^{n}h(T)\sum_{d|T}f(d)g(\frac{T}{d})$$设$F(n)=\sum_{d|n}f(d)g(\frac{n}{d})$，则原式可化为$$\sum_{T=1}^{n}h(T)F(T)$$如果两个函数一个可以整除分块，另一个可以用$O(1)/O(n \log n)/O(n)/O(n^{\frac{2}{3}})$求出前缀和，那么就可以以较低时间复杂度求出答案。

$$\sum_{i=1}^ni[\gcd(i,n)=1]=\frac{n\varphi(n)+[n=1]}{2}$$ 证明如下：$$\sum_{i=1}^ni[\gcd(i,n)=1]$$ 套用$\epsilon = \mu * 1$ $$=\sum_{i=1}^ni\sum_{d|\gcd(i,n)}\mu(d)$$ 枚举$d$，注意这里$n$是已知量，只需枚举$d|n$ $$=\sum_{d|n}\mu(d)d\sum_{i=1}^{\frac{n}{d}}i$$ $$=\frac{1}{2}\sum_{d|n}\mu(d)d\frac{n}{d} ( \frac{n}{d} + 1)$$ $$=\frac{n}{2}\sum_{d|n}\mu(d)( \frac{n}{d} + 1)$$ $$=\frac{n}{2}(\sum_{d|n}\mu(d)\frac{n}{d}+\sum_{d|n}\mu(d))$$ 由$\varphi= \mu * \operatorname{id}$和$\epsilon = \mu * 1$可得$$=\frac{n}{2}(\varphi(n)+[n=1])$$ $$=\frac{n\varphi(n)+n[n=1]}{2}$$ $$=\frac{n\varphi(n)+[n=1]}{2}$$

$$\varphi(nm)=\frac{\varphi(n)\varphi(m)\gcd(n,m)}{\varphi(\gcd(n,m))}$$ 只需将欧拉函数展开，提取出$n$与$m$的公共质因子即可证明。