注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.9 $\varphi$ 与 $\mu$ 的旁注。
P111 最上方的推导
$$
n \perp m \Leftrightarrow n \perp m_1 , n \perp m_2
$$
$$
\Leftrightarrow \gcd(n, m_1) = 1, \gcd(n, m_2) = 1
$$
$$
\Leftrightarrow \gcd(n \bmod m_1, m_1) = 1, \gcd(n \bmod m_2, m_2) = 1
$$
$$
\Leftrightarrow n \bmod m_1 \perp m_1, n \bmod m_2 \perp m_2
$$
P111 “好的”的推导
这里的将互素定义为“好的”的一系列论述让人摸不着头脑。其实它就是指出互素的充要条件。然后注意 $n < m$，所以整个逻辑链可以构成递推：
$$
n \bmod m \perp m \Leftrightarrow n \bmod m_1 \perp m_1, n \bmod m_2 \perp m_2
$$
这个可以一直往下递推到素数 (以及素数的幂) 的情况。
注意：有一点原文中讲的有些含糊，那就是：
根据独立剩余得到的性质，我们任取 $n \bmod m_1$ 与 $n \bmod m_2$ 的值，总能找到唯一的 $0 \leq n < m$ 使之成立。这是这个递推能够成立的至关重要的一点！
完成了上面的论述，我们便有：
$$
\varphi(m) = \varphi(m_1) \varphi(m_2), m_1\perp m_2, m = m_1m_2
$$
P111 $\varphi$ 函数公式推导的补充
$$
\begin{aligned}
\varphi(m) &= \prod _{p\mid m} \varphi(p^{m_p}) \\
&= \prod _{p\mid m} (p^{m_p} - p^{m_p-1}) \\
&= \prod _{p\mid m} p^{m_p} \Big (1 - \frac 1 p \Big) \\
&= \prod _{p\mid m} p^{m_p} \prod _{p\mid m}\Big (1 - \frac 1 p \Big) \\
&= m \prod _{p\mid m}\Big (1 - \frac 1 p \Big) \\
\end{aligned}
$$
P112 为什么 $\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)+\varphi(6)+\varphi(12)=12$?
求证：对于 $d\mid m$，$\displaystyle \frac i d (i \leq d)$一定出现在 $\displaystyle \frac j m (j \leq m)$ 中。
证明：
$$
\frac i d = \frac i d \frac {m/d}{m/d} = \frac {im/d} {m}, \frac {im}d \leq m
$$
所以我们可以知道：对于 $\displaystyle \frac j {12}$，约分后的最简分数 $\displaystyle\frac i d$ 一定有 $i \perp d$，且根据我们证明的引理，$\forall i \in [0..d), i \perp d$ 一定会出现原分数组 $\displaystyle \frac j {12}$ 中。
故
$$
\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)+\varphi(6)+\varphi(12)=12
$$
用同样的方式推广，即
$$
\sum_{d\mid m} \varphi(d) = m
$$
P112 $g$ 是积性的则 $f$ 必然是积性的，证明补充
稍作补充。对于 $m=1$
$$
g(1) = \sum _{d\mid 1} f(d) = f(1) = 1
$$
其中 $g(1)=1$ 是积性函数的定义。
对于 $m > 1$，根据归纳假设，$m_1m_2 < m, m_1\perp m_2$ 时有 $f(m_1)f(m_2) = f(m_1m_2)$，我们现在需要证明 $m_1m_2 = m$ 的情况。
$$
\begin{aligned}
g(m_1m_2) &= \boxed{\sum _{d \mid m_1m_2} f(d) = \sum_{d_1\mid m_1}\sum_{d_2\mid m_2} f(d_1d_2)}^{\text{ note: }1} \\
&= \Big (\sum_{d_1\mid m_1}\sum_{d_2\mid m_2} f(d_1)f(d_2)\Big ) - f(m_1)f(m_2) + f(m_1m_2) \\
&= \Big (\sum_{d_1\mid m_1} f(d_1)\sum_{d_2\mid m_2}f(d_2)\Big ) - f(m_1)f(m_2) + f(m_1m_2) \\
&= g(m_1)g(m_2) - f(m_1)f(m_2) + f(m_1m_2)
\end{aligned}
$$
下面是方框的注释：
- 因为 $m_1 \perp m_2$，所以 $\gcd(d_1, d_2)=1$
又因为 $g$ 是积性的，所以
$$
g(m_1m_2) = g(m_1)g(m_2)
$$
所以
$$
f(m_1m_2) = f(m_1) f(m_2)
$$
故 $f$ 也是积性的。
P112 $f$ 是积性的则 $g$ 必然是积性的
证明:
$$
\begin{aligned}
g(m_1m_2) &= \sum _{d \mid m_1m_2} f(d) = \sum_{d_1\mid m_1}\sum_{d_2\mid m_2} f(d_1d_2) \\
&= \sum_{d_1\mid m_1}\sum_{d_2\mid m_2} f(d_1)f(d_2) \\
&= \sum_{d_1\mid m_1} f(d_1)\sum_{d_2\mid m_2}f(d_2) \\
&= g(m_1)g(m_2) & \square
\end{aligned}
$$
