数论函数

积性函数

加性函数

等价性

卷积

符号

• 在 $x=1$ 时，易证。
• 在 $x$ 为质数时，$d$ 只能为 $1$ 或 $x$，又有 $\varphi(1)=1,\varphi(x)=x-1$，故 $\sum_{d\mid x}\varphi(d)=x$ 成立。
• 在 $x$ 为合数且不为 $1$ 时，不妨构造 $x$ 个分数 $\dfrac{1\sim x}{x}$，化简后分母只有 $x$ 的因数，且由于分子和分母互质，所以以因数 $d$ 为分母的分数有且仅有 $\varphi(d)$ 个，又因为共有 $x$ 个分数，所以 $\sum_{d\mid x}\varphi(d)=x$ 成立。

• 在 $x=1$ 时，易证。
• 在 $x\not= 1$ 时，根据唯一分解定理，有 $x=\prod_{i=1}^s p_i^{a_i}$，由于在 $x$ 有相同质因子时 $\mu(x)=0$，因此可以构造 $x'=\prod_{i=1}^sp_i$ 使得 $\sum_{d\mid x}\mu(d)=\sum_{d\mid x'}\mu(d)$。则：
  • 不含质因子的 $d$（即 $1$）有 $C_s^0$ 个，$\mu(d)$ 为正；
  • 含一个质因子的 $d$ 有 $C_s^1$ 个，$\mu(d)$ 为负；
  • 含两个质因子的 $d$ 有 $C_s^2$ 个，$\mu(d)$ 为正；
  • $\dots$
• 于是 $\sum_{d\mid x'}\mu(d)=\sum_{i=0}^s(-1)^s C_s^i$，由二项式定理，$\sum_{i=0}^s(-1)^s C_s^i=(1-1)^s=0$。

• 在 $x=1$ 时，易证。
• 在 $x\not= 1$ 时，同上文构造 $x'=\prod_{i=1}^sp_i$ 使得 $\sum_{d\mid x}\mu(d)\dfrac{x}{d}=\sum_{d\mid x'}\mu(d)\dfrac{x'}{d}=x'\sum_{d\mid x'}\dfrac{\mu(d)}{d}$。又有 $x'\sum_{d\mid x'}\dfrac{\mu(d)}{d}=x(1-(\dfrac{1}{p_1}+\dfrac{1}{p_2}+\dots)+(\dfrac{1}{p_1p_2}+\dfrac{1}{p_2p_3}+\dots)-\dots)$（这步即通过 $\mu(d)$ 的定义判断 $\dfrac{\mu(d)}{d}$ 的正负性），因式分解得 $x(1-(\dfrac{1}{p_1}+\dfrac{1}{p_2}+\dots)+(\dfrac{1}{p_1p_2}+\dfrac{1}{p_2p_3}+\dots)-\dots)=x'\prod_{i=1}^s1-\dfrac{1}{p_i}$，即 $\varphi(x)$。