注：本节内容为《具体数学》(原书第二版) 第四章 数论 基础题的答案。

4.14

(a)

$$
\begin{aligned}
~& \gcd(km, kn) = t \\
\Leftrightarrow ~& t_p = \min(k_p+m_p,k_p+n_p) \\
\Leftrightarrow ~& t_p = k_p + \min(m_p,n_p) \\
\Leftrightarrow ~& t_p - k_p = \min(m_p,n_p) \\
\Leftrightarrow ~& \frac t k = \gcd(m,n), \text{According to (4.12)} \\
\Leftrightarrow ~& k\gcd(m,n) = \gcd(km, kn)
\end{aligned}
$$

(b)

$$
\begin{aligned}
~&\operatorname{lcm}(k m, kn)=t \\
\Leftrightarrow ~& t_{p}=\max \left(k_{p}+k_{m}, k_{p}+k_{n}\right) \\
\Leftrightarrow ~& t_{p}=k_{p}+\max \left(k_{m}, k_{n}\right) \\
\Leftrightarrow ~& t_{p}-k_{p}=\max \left(k_{m}, k_{n}\right) \\
\Leftrightarrow ~& \frac{t}{k}=\operatorname{lcm}(m, n), \text{According to (4.12)} \\
\Leftrightarrow ~& k \operatorname{lcm}(m, n)=\operatorname{lcm}(k m, k n) \\
\end{aligned}
$$

4.15

不可能

引理 1：除了 $e_1$，所有欧几里得数都是奇数。

证明：根据欧几里得数的构造，每两个欧几里得数都互相互素，而 $e_1 = 2$，故后面的欧几里得数都必然不是偶数，为奇数。

引理 2：所有欧几里得数同余 $5$ 交替于 $2$ 与 $3$。

证明：通过归纳法证明：

$e_1 = 2$，$e_2 = 3$，成立。

设对于所有 $k \leq 2n$ 题设都成立。

对于

$$
e_{2n+1} = \prod_{k=1}^{2n} e_k + 1 \equiv (2 \times 3) ^ n + 1 \equiv 1^n+1 \equiv 2 \pmod 5
$$

$$
e_{2n+2} = e_{2n}\prod_{k=1}^{2n} e_k + 1 \equiv 2 \times 1^n + 1 \equiv 3 \pmod 5
$$

Q.E.D.

故根据引理 2，素数 $5$ 不是任何一个欧几里得数的因子。

4.16

可由归纳法证得

$$
\sum_{i=1}^n \frac 1 {e_i} = 1 - \frac 1 {e_{n+1} - 1}
$$

证明：

$$
\sum_{i=1}^{n+1} \frac 1 {e_i} = 1 - \frac 1 {e_{n+1} - 1} + \frac 1 {e_{n+1}} = 1 - \frac 1 {e_{n+1}(e_{n+1} - 1)} = 1 - \frac 1 {e_{n+2}}
$$

4.17

当 $n > m$ 时，我们有

$$
2^{2^n} = 2^{2^m2^{n-m}} = \left(2^{2^m}\right)^{2^{n-m}}
$$

$$
\begin{aligned}
2^{2^n} &= 2^{2^n} + 2^{2^m} - 2^{2^m} \\
&= \left(2^{2^m}\right)^{2^{n-m}} + 2^{2^m} - 2^{2^m} \\
&= 2^{2^m}\left(1 + \left(2^{2^m}\right)^{2^{n-m}-1}\right) - 2^{2^m} \\
&= 2^{2^m}\left(1 + 2^{2^m}\right)\left( \left(2^{2^m}\right)^{2^{n-m}-2} - \left(2^{2^m}\right)^{2^{n-m}-3} + \cdots - \left(2^{2^m}\right)^{1} + 1 \right) - 2^{2^m}
\end{aligned}
$$

$$
2^{2^m}\left( \left(2^{2^m}\right)^{2^{n-m}-2} - \left(2^{2^m}\right)^{2^{n-m}-3} + \cdots - \left(2^{2^m}\right)^{1} + 1 \right) = \frac {2^{2^n} + 2^{2^m}} {2^{2^m}+1}
$$

所以

$$
\begin{aligned}
\left\lfloor \frac {f_n} {f_m} \right\rfloor &= \left\lfloor \frac {2^{2^n}+1} {2^{2^m}+1} \right\rfloor \\
&= \left\lfloor \frac {2^{2^m}\left(1 + 2^{2^m}\right)\left( \left(2^{2^m}\right)^{2^{n-m}-2} - \left(2^{2^m}\right)^{2^{n-m}-3} + \cdots - \left(2^{2^m}\right)^{1} + 1 \right) - 2^{2^m}+1} {2^{2^m}+1} \right\rfloor \\
&= 2^{2^m}\left( \left(2^{2^m}\right)^{2^{n-m}-2} - \left(2^{2^m}\right)^{2^{n-m}-3} + \cdots - \left(2^{2^m}\right)^{1} + 1 \right) + \left\lfloor \frac {1 - 2^{2^m}} {2^{2^m}+1} \right\rfloor \\
&= 2^{2^m}\left( \left(2^{2^m}\right)^{2^{n-m}-2} - \left(2^{2^m}\right)^{2^{n-m}-3} + \cdots - \left(2^{2^m}\right)^{1} + 1 \right) - \left\lceil \frac {2^{2^m}-1} {2^{2^m}+1} \right\rceil \\
&= \frac {2^{2^n} + 2^{2^m}} {2^{2^m} + 1} - \left\lceil \frac {2^{2^m}-1} {2^{2^m}+1} \right\rceil = \frac {2^{2^n} + 2^{2^m}} {2^{2^m} + 1} - 1 = \frac {2^{2^n} - 1} {2^{2^m} + 1}
\end{aligned}
$$

所以

$$
\begin{aligned}
f_n \bmod f_m = f_n - f_m\left\lfloor \frac {f_n} {f_m} \right\rfloor = 2^{2^n} + 1 - \frac {2^{2^n} - 1} {2^{2^m} + 1}({2^{2^m} + 1}) = 2
\end{aligned}
$$

故根据欧几里得递推式

$$
\gcd(f_n, f_m) = \gcd(f_n \bmod f_m, f_m) = \gcd(f_m, 2) = 1
$$

即

$$
f_n \perp f_m
$$

4.18

试证逆否命题：

若 $n$ 不是 $2$ 的幂次，则 $2^n + 1$ 为合数。

证明：

根据题设，$n$ 可表示为

$$
n = qm, q \text{ is odd}
$$

则

$$
2^n + 1 = (2^m + 1) (2^{n-m} - 2^{n-2m} + \cdots - 2^{m} + 1)
$$

4.19

试证：

$$
\begin{aligned}
\sum_{1 \leqslant k<n}\left\lfloor\frac{\varphi(k+1)}{k}\right\rfloor &=\sum_{1<m \leq n}\left\lfloor\left(\sum_{1 \leqslant k<m}\lfloor(m / k) /\lceil m / k\rceil\rfloor\right)^{-1}\right\rfloor \\
&=n-1-\sum_{k=1}^{n}\left\lceil\left\{\frac{(k-1) !+1}{k}\right\}\right\rceil
\end{aligned}
$$

证明：

考察等式左边的求和项

$$
\left\lfloor\frac{\varphi(k+1)}{k}\right\rfloor
$$

根据 $\varphi$ 函数的性质：

$$
\varphi(k + 1) \leq k
$$

而 $\displaystyle \left\lfloor\frac{\varphi(k+1)}{k}\right\rfloor = 1 \Leftrightarrow \varphi(k+1)=k$ 当且仅当 $k$ 是素数。所以等式左侧即为

$$
\sum_{1 \leqslant k<n}\left\lfloor\frac{\varphi(k+1)}{k}\right\rfloor = \pi(n)
$$

类似地，考察右侧第一个式子：

$$
\left \lfloor \frac {\frac m k} {\left \lceil \frac m k \right \rceil} \right \rfloor =1 \Leftrightarrow \frac {\frac m k} {\left \lceil \frac m k \right \rceil} = 1 \Leftrightarrow {\frac m k} = {\left \lceil \frac m k \right \rceil} \Leftrightarrow k \backslash m
$$

故

$$
\sum_{1 \leqslant k<m}\lfloor(m / k) /\lceil m / k\rceil\rfloor = \sum_{1\leqslant k < m}[k\backslash m]
$$

$$
\begin{aligned}
\sum_{1<m \leq n}\left\lfloor\left(\sum_{1 \leqslant k<m}\lfloor(m / k) /\lceil m / k\rceil\rfloor\right)^{-1}\right\rfloor = \sum_{1<m \leq n}\left\lfloor\left(\sum_{1\leqslant k < m}[k\backslash m]\right)^{-1}\right\rfloor
\end{aligned}
$$

接下来我们来考察其内部：

易得

$$
\left\lfloor\left(\sum_{1\leqslant k < m}[k\backslash m]\right)^{-1}\right\rfloor \leq 1
$$

且

$$
\left\lfloor\left(\sum_{1\leqslant k < m}[k\backslash m]\right)^{-1}\right\rfloor =1 \Leftrightarrow \sum_{1\leqslant k < m}[k\backslash m] = 1 \Leftrightarrow [m \in P]
$$

故等式右侧亦为 $\pi(n)$

$$
\sum_{1<m \leq n}\left\lfloor\left(\sum_{1 \leqslant k<m}\lfloor(m / k) /\lceil m / k\rceil\rfloor\right)^{-1}\right\rfloor = \sum_{1<m \leq n} [m\in P] = \pi(n)
$$

最后，我们来分析最后一个式子：

$$
n-1-\sum_{k=1}^{n}\left\lceil\left\{\frac{(k-1) !+1}{k}\right\}\right\rceil
$$

不难看出

$$
\left\lceil\left\{\frac{(k-1) !+1}{k}\right\}\right\rceil = 0 \Leftrightarrow \left\{\frac{(k-1) !+1}{k}\right\} = 0 \Leftrightarrow k \backslash [(k-1) !+1]
$$

根据威尔逊定理，等价于

$$
k \in P, k > 1
$$

故最后一个式子中的和式减去的都是不是素数的数，故最后留下来的就是素数的个数，故也为 $\pi(n)$。Q.E.D.

4.20

构造见答案。这里证明答案的正确性。

若 $b = \lg^{(n)} p_n$，那么 $\displaystyle\left\lfloor 2^b \right\rfloor, \left\lfloor 2^{2^b} \right\rfloor, \left\lfloor 2^{2^{2^b}} \right\rfloor, \cdots, \left\lfloor \underbrace{2^{\cdot^{\cdot^{\cdot ^{2^b}}}}}_{n} \right\rfloor$ 都是素数。

证明：

考察第 $n$ 项：

$$
\left\lfloor \underbrace{2^{\cdot^{\cdot^{\cdot ^{2^b}}}}}_{n} \right\rfloor = \lfloor p_n \rfloor = p_n
$$

为素数。

考察第 $n-1$ 项：

$$
\left\lfloor \underbrace{2^{\cdot^{\cdot^{\cdot ^{2^b}}}}}_{n-1} \right\rfloor = \left\lfloor \lg p_n \right\rfloor
$$

根据构造

$$
2^{p_{n-1}} < p_n < 2^{p_{n-1}+1} \Rightarrow p_{n-1} < \lg p_n < p_{n-1} + 1
$$

所以

$$
\left\lfloor \lg p_n \right\rfloor = p_{n-1}
$$

为素数。

不难看出，我们可以使用归纳法证得这些数都是素数。

然后这里规避了一个问题：

$$
\lim_{n\rightarrow \infty} \lg^{(n)}p_n
$$

是否存在？答案是肯定的。我们这就来证明。

首先证明 $\lg^{(n)}p_n$ 上下有界：

根据定义：

$$
\underbrace{2^{\cdot^{\cdot^{\cdot ^{2^2}}}}}_{n} < \cdots < 2^{2^{p_{n-2}}} < 2^{p_{n-1}} < p_n < 2^{p_{n-1}+1} < 2^{2^{p_{n-2}+1}+1} < \cdots < \underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+1}+1}}_{n}
$$

所以

$$
\underbrace{2^{\cdot^{\cdot^{\cdot ^{2^2}}}}}_{n} < p_n < \underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+1}+1}}_{n}
$$

故显然有下界:

$$
\lg^{(n)}p_n > 1
$$

上界则比较难分析：

$$
\begin{aligned}
\lg^{(n)}p_n &< \lg^{(n)}\underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+1}+1}}_{n} \\
&= \lg^{(n-1)}\left (\underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+1}}}_{n-1}+1 \right ) \\
&< \lg^{(n-1)}\left (\underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+1}}}_{n-1}\times 2 \right ) \\
&= \lg^{(n-1)}\left (\underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+2}}}_{n-1} \right ) \\
&= \lg^{(n-2)}\left (\underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+1}}}_{n-2}+2 \right ) \\
&< \lg^{(n-2)}\left (\underbrace{2^{\cdot^{\cdot^{\cdot ^{2^{2+1}}}\ddots+1}}}_{n-2} \times 2 \right ) \\
&\cdots \\
&< \lg^{(2)} \left ( 2^{2+1} + 2 \right) \approx 1.91795
\end{aligned}
$$

故上界亦存在。

接下来我们证明 $\lg^{(n)}p_n$ 是递增的。这是显然的。因为根据定义

$$
\begin{aligned}
&2^{p_{n}} < p_{n+1} < 2^{p_{n}+1} \\
\Rightarrow~ & \lg p_{n+1} > p_n \\
\Rightarrow~ & \lg^{(n)}\lg p_{n+1} > \lg^{(n)} p_n \\
\Rightarrow~ & \lg^{(n+1)} p_{n+1} > \lg^{(n)} p_n
\end{aligned}
$$

Q.E.D.

4.21

构造见答案。这里证明答案的正确性。

证明：

根据贝特朗假设，我们有：

$$
1 < p \leq 2
$$

$$
2 < p \leq 4
$$

$$
4 < p \leq 8
$$

$$
\cdots
$$

由于这些区间互相独立且并集可以构成整个正整数集，我们便可以给这些素数都加上下标。

$$
1 < P_1 \leq 2
$$

$$
2 < P_2 \leq 4
$$

$$
4 < P_3 \leq 8
$$

$$
\cdots
$$

所以

$$
2^{n-1} < P_n \leq 2^{n} < 10^n
$$

令

$$
{K}=\sum_{{k} \geqslant 1} 10^{-{k}^{2}} {P}_{{k}}=.200300005 \ldots
$$

则

$$
\begin{aligned}
&\left\lfloor\left(10^{n^{2}} K\right) \bmod 10^{n}\right\rfloor \\
=&\left\lfloor\left(10^{n^{2}} \sum_{{k} \geqslant 1} \frac {{P}_{{k}}} {10^{{k}^{2}}}\right) \bmod 10^{n}\right\rfloor \\
\end{aligned}
$$

其中

$$
P_k < 10^k \Rightarrow \frac {P_k} {10^k} < 1\Rightarrow \frac {P_k} {10^{k^2}} < \frac {10^k} {10^{k^2}} = \frac {1} {10^{k^2-k}}
$$

但是和式仍然十分复杂，所以我们不妨对于 $k$ 的大小拆开分析：

$$
\begin{aligned}
&\left\lfloor\left(10^{n^{2}} \sum_{{k} \geqslant 1} \frac {{P}_{{k}}} {10^{{k}^{2}}}\right) \bmod 10^{n}\right\rfloor \\ =& \left\lfloor10^{n^{2}}\left(\frac {P_n} {10^{n^2}} + \sum_{1 \leqslant {k} < n} \frac {{P}_{{k}}} {10^{{k}^{2}}} + \sum_{{k} > n} \frac {{P}_{{k}}} {10^{{k}^{2}}}\right) \bmod 10^{n}\right\rfloor
\end{aligned}
$$

对于 $k > n \geq 1$ ，令 $k = n + \Delta k, \Delta k > 0$，有

$$
\begin{aligned}
10^{n^2}\frac {P_k} {10^{k^2}} &< \frac {10^{n^2}} {10^{k^2-k}} \\
&= 10^{n^2-k^2+k} \\
&\leq 10^{n-2n\Delta k + \Delta k - \Delta k^2} \\
&\leq 10^{n-2n\Delta k - \Delta k + 1} \\
&\leq 10^{-n - \Delta k + 1}
\end{aligned}
$$

故

$$
10^{n^{2}} \sum_{{k} \geqslant 1} \frac {{P}_{{k}}} {10^{{k}^{2}}}=\sum_{k=n+1}^{\infty}10^{n^2}\frac {P_k} {10^{k^2}} < \sum_{\Delta k = 1}^{\infty} 10^{-n-\Delta k + 1} \leq 1
$$

对于 $1 \leq k < n$，我们有

$$
10^{n^2}\frac {P_k} {10^{k^2}} = P_k 10^{n^2-k^2} = P_k10^{2n-1} \times10^{n^2-k^2-2n+1}
$$

其中 $n^2-k^2-2n+1 \geq 0$。所以

$$
10^{n^2}\frac {P_k} {10^{k^2}} \equiv 0 \pmod {10^{2n-1}} \Rightarrow 10^{n^2}\frac {P_k} {10^{k^2}} \equiv 0 \pmod {10^{n}}
$$

接下来带入回拆分后的原式：

$$
\begin{aligned}
&\left\lfloor10^{n^{2}}\left(\frac {P_n} {10^{n^2}} + \sum_{1 \leqslant {k} < n} \frac {{P}_{{k}}} {10^{{k}^{2}}} + \sum_{{k} > n} \frac {{P}_{{k}}} {10^{{k}^{2}}}\right) \right\rfloor \\
\equiv &\left\lfloor P_n + 0 + \epsilon \right\rfloor \pmod {10^{n}}, 0 < \epsilon < 1 \\
\equiv & P_n \pmod {10^{n}}
\end{aligned}
$$

因为 $P_n < 10^n$，所以有

$$
\left\lfloor\left(10^{n^{2}} \sum_{{k} \geqslant 1} \frac {{P}_{{k}}} {10^{{k}^{2}}}\right) \bmod 10^{n}\right\rfloor = \left\lfloor\left(10^{n^{2}} K\right) \bmod 10^{n}\right\rfloor = P_n
$$

4.22

试证逆否命题：

$$
(11\cdots 11)_b
$$

中 $1$ 的个数不是素数，则此数必定不是素数。

证明：

设 $1$ 的个数为 $n$。因为 $n$ 不是素数，故有两种情况：

(1) $n = 1$，原数为 $1$ 不是素数，成立。

(2) $n$ 为合数，我们能找到一个 $d \backslash n, d > 1$

所以

$$
\underbrace{(11\cdots 11)_b}_{n} = \underbrace{\underbrace{(1\cdots 1)}_{d} \cdots \underbrace{(1\cdots 1)_b}_{d}}_{n / d}
$$

接下来的分解留给读者思考。

4.23

不难给出通式：

$$
\rho (x) = \sum_{k \geq 1} [2^k \backslash x]
$$

同样不难看出：

$$
\rho (2x) = \rho(x) + 1, x \geq 1
$$

$$
\rho (2x + 1) = 0
$$

关于与河内塔的关联，答案已经给出，不再详述。有兴趣的话可以用归纳法证得。

4.24

$$
\epsilon_{p}(n !)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^{2}}\right\rfloor+\left\lfloor\frac{n}{p^{3}}\right\rfloor+\cdots=\sum_{k \geqslant 1}\left\lfloor\frac{n}{p^{k}}\right\rfloor
$$

思考将 $n$ 表达成 $p$ 进制。

$$
(\cdots a_1 a_0) _p
$$

这个和式就是右位移求和。思考每一个数位 $a_k$ 在此过程中的贡献，让我们记其为 $s_k$

$$
s_k = a_k ( p^0 + p^1 + \cdots + p^{k-1} ) = a_k \frac {p^k - 1} {p - 1} = \frac {a_k p^k} {p-1} - \frac {a_k} {p-1}
$$

对 $s_k$ 求和，我们就能得到 $\epsilon_p(n!)$:

$$
\begin{aligned}
\epsilon_p(n!) &= \sum_k s_k = \sum_k \left ( \frac {a_k p^k} {p-1} - \frac {a_k} {p-1} \right ) \\&= \frac 1 {p-1} \left ( \sum_ {k} a_k p^k - \sum_k a_k \right) = \frac {n - v_p(n)} {p - 1}
\end{aligned}
$$

4.25

(a)

$k\perp m$，试证

$$
k \backslash\backslash n, m \backslash\backslash n \Leftrightarrow km \backslash\backslash n
$$

证明：

$$
k \backslash\backslash n, m \backslash\backslash n
$$

等价于

$$
\gcd(n/k, k) = \gcd(n/m, m) = 1
$$

等价于

$$
\min(n_p - k_p, k_p) = 0
$$

$$
\min(n_p - m_p, m_p) = 0
$$

因为 $k \perp m$，所以

$$
m_p k_p = 0
$$

故可推出

$$
\min(n_p - k_p - m_p, k_p + m_p) = \min(n_p - \max (k_p, m_p), \max (k_p, m_p)) = 0
$$

即

$$
km \backslash\backslash n
$$

现在我们反过来证明。假设 $km \backslash\backslash n$ 成立，则

$$
\min(n_p - \max (k_p, m_p), \max (k_p, m_p)) = 0
$$

对于 $m_p \neq 0$ 与 $k_p \neq 0$ 分别可推出：

$$
\min(n_p - m_p, m_p) = 0, m_p \neq 0
$$

$$
\min(n_p - k_p, k_p) = 0, k_p \neq 0
$$

同时等于 $0$ 的情况显然成立，因为 $n_p \geq 0$

由于都是等价变换。证毕。

(b)

不成立。

取 $\gcd(m,n)=12, m = 24, n = 36$ 即可推翻。

4.26

可以证明，$\mathcal G_N$ 为 Stern-Brocot Tree 的一颗子树。

证明：

若 $\mathcal G_N$ 不是 Stern-Brocot Tree 的一颗子树，那么可能会有如下情况：

• 不递增【根据构造，排除】
• 不是最简分数【根据构造，排除】
• 儿子元素出现，然而父亲元素不出现。

我们着重证明第三种情况不可能发生。因为儿子元素的分子分母大于任意父亲元素的分子分母，根据 $m'n'\leq N$ 可知 $mn < N$。

故 $\mathcal G_N$ 一定是 Stern-Brocot Tree 的一颗子树。

而 $m'n-n'm=1$ 是 Stern-Brocot Tree 子树的性质，故一定为真。

4.27

见答案，容易得出。总体思路就是字典序。

4.28

打表易得。

4.29

由构造法可知，Stern-Brocot Tree 以中间的 $\frac 1 1$ 为界，左右对称，除了会交换分子分母的位置，因为左侧是 $\frac 0 1, \frac 1 1$，右侧是 $\frac 1 1 \frac 1 0$。这个结论可以对 Stern-Brocot Tree 的每一层的数的情形做归纳证得。

此外，我们发现，如果将构造序列中的 L 与 R 交换，我们就达到的两个位置关于 $\frac 1 1$ 对称。

结合第一个结论，我们可知，交换构造序列的 L 和 R 可以得到一对倒数。

题目中 $x$ 是一个二进制序列 $(.b_1b_2b_3\cdots)_2$，而 $1-x = (.\bar{b_1}\bar{b_2}\bar{b_3}\cdots)_2$，其中 $\bar{b} = 1 - b$。故 $1-x$ 对应的构造序列就是 L 和 R 交换的序列。所以我们可以得到 $1 / \alpha$。

4.30 中国剩余定理

已独立写成文章。

4.31

证明：

我们不妨首先将这个数表示为

$$
(a_n a_{n-1} \cdots a_0)_{10}
$$

因为

$$
10 \equiv 1 \pmod 3
$$

所以我们有

$$
10^n \equiv 1 \pmod 3
$$

$$
a_n 10^n \equiv a_n \pmod 3
$$

故

$$
\begin{aligned}
a &= \sum_{k=0}^n a_k 10^k \\
&\equiv \sum_{k=0}^n a_k \pmod 3
\end{aligned}
$$

Q.E.D.

推广：

对于 $b$ 进制数，若 $b \equiv 1 \pmod m$，则这个数能被 $m$ 整除等价于这个数在 $b$ 进制下的数位表示之和能够被 $d$ 整除。

4.32

见其他文章。欧拉定理专门写过一篇文章证明过。

4.33

若 $f(m)$ 和 $g(m)$ 都为积性函数，则对于 $m = m_1m_2, m_1 \perp m_2$，我们总有：

$$
f(m) = f(m_1)f(m_2)
$$

$$
g(m) = g(m_1)g(m_2)
$$

且

$$
f(1) = g(1) = 1
$$

接下来我们看 $h(m)$

$$
h(1) = \sum_{d\backslash 1} f(d)g(m/d) = f(1)g(1) = 1
$$

满足条件，再看一般的 $m_1 \perp m_2$:

$$
\begin{aligned}
h(m_1m_2) &= \sum_{d\backslash m_1m_2} f(d) g(m_1m_2/d) \\
&= \sum_{d = 1, m_1, m_2, m_1m_2} f(d) g(m_1m_2/d) \\
&=f(1)g(m_1m_2) + f(m_1)g(m_2)+f(m_2)g(m_1)+f(m_1m_2)g(1) \\
&=g(m_1)g(m_2) + f(m_1)g(m_2) + f(m_2)g(m_1) + f(m_1)f(m_2) \\
&=(g(m_1) + f(m_1))(g(m_2)+f(m_2)) \\
&=\left(\sum_{d\backslash m_1} f(d)g(m_1/d)\right)\left(\sum_{d\backslash m_2} f(d)g(m_2/d)\right) \\
&=h(m_1)h(m_2)
\end{aligned}
$$

所以 $h(m)$ 为积性函数。Q.E.D.

4.34

试证前者为后者的特例。

$$
g(m) = \sum_{d\mid m}f(d) \Leftrightarrow f(m)=\sum_{d \mid m} \mu(d) g\left(\frac{m}{d}\right)
$$

$$
g(x) = \sum_{d \geq 1} f\left(\frac x d\right) \Leftrightarrow f(x) = \sum_{d \geq 1} \mu(d) g\left(\frac xd\right)
$$

我们不妨先把前者写为与后者更加相符的等价形式：

$$
g(m) = \sum_{d\mid m}f\left(\frac m d\right) \Leftrightarrow f(m)=\sum_{d \mid m} \mu(d) g\left(\frac{m}{d}\right)
$$

接下来我们开始证明：

我们设函数 $f, g$ 满足莫比乌斯反演，且都为定义在整数集上的函数，即

$$
f(x) = 0, x \notin \mathbb Z
$$

$$
g(x) = 0, x \notin \mathbb Z
$$

则有

$$
g(m) = \sum_{d \geq 1} f\left(\frac m d\right) = \sum_{d \backslash m} f\left(\frac m d\right)
$$

$$
f(m)=\sum_{d \geq 1} \mu(d) g\left(\frac md\right)=\sum_{d \backslash m} \mu(d) g\left(\frac{m}{d}\right)
$$

此时，由于普遍莫比乌斯反演成立，我们便能推出特殊的莫比乌斯反演。