狄利克雷卷积 常用结论

(varphi * I = id)

证明这个东西其实就是证明欧拉函数的性质：(sum_{d|n} varphi(d) = n)

两种方法：
1.

首先写出(frac{1}{n} frac{2}{n} frac{3}{n} ... frac{n}{n})

然后将这些分数化至最简分数

那么此时的分母一定对应着一个d 而此时的分子一定与分母是互质的 所以(varphi(n)) 其实就是分母为n的分数有多少个

所以(sum_{d|n} varphi(d)) 按照上面的方式理解，就是各个分母数量之和，显然等于n

设(f(n) = sum_{d|n} varphi(d))

先来证明(f)是个积性函数

令(n) 与 (m) 互质

那么(f(n) * f(m) = sum_{d|n} varphi(d) * sum_{k|m} varphi(k))

(f(n) * f(m) = sum_{d|n} sum_{k|m} varphi(d) * varphi(k))

(f(n) * f(m) = sum_{d|n} sum_{k|m} varphi(d*k))

因为(nm)互质 所以原式等价于

(f(n) * f(m) = sum_{d*k|n*m} varphi(d*k))

令(D=d*k)

(f(n) * f(m) = sum_{D|n*m} varphi(D))

(f(n) * f(m) = f(n*m))

得证

令(n = p_1^{c_1} * p_2^{c_2} * p_3^{c_3} * ... * p_k^{c_k})

则(f(n) = sum_{d|n} varphi(d))

(f(n) = sum_{d_1|{p_1^{c_1}}} varphi(d_1) * sum_{d_2|{p_2^{c_2}}} varphi(d_2) * sum_{d_3|{p_3^{c_3}}} varphi(d_3) * sum_{d_k|{p_k^{c_k}}} varphi(d_k))

(f(n) = f(p_1^{c_1}) * f(p_2^{c_2}) * f(p_3^{c_3} ) * ... * f(p_k^{c_k}))

又(f(p^k) = varphi(p) + varphi(p^2) + varphi(p^3) + ... + varphi(p^k))

所以得到(f(p^k) = 1 + p-1 + p^2-p + p^3-p^2+...+p^k-p^{k-1} = p^k)

(f(p_1^{c_1}) * f(p_2^{c_2}) * f(p_3^{c_3} ) * ... * f(p_k^{c_k}) = p_1^{c_1} * p_2^{c_2} * ... * p_k^{c^k})

右边等于(n)

所以(f(n) = n)

原式得证

(mu * I = e)

莫比乌斯函数性质

用二项式定理即可

(mu * id = varphi)

首先(varphi * I = id)

同乘(mu)

(varphi * I * mu = id * mu)

(varphi * e = id * mu)

(varphi = id * mu)