注：本节内容为《具体数学》(原书第二版) 第四章 数论 热身题的答案。
4.1
略
4.2
(1)
$$
k = \gcd(m,n) \Leftrightarrow k_p = \min (m_p, n_p)
$$
$$
k = \operatorname{lcm}(m,n) \Leftrightarrow k_p = \max (m_p, n_p)
$$
$$
k = \gcd(m,n) \operatorname{lcm}(m,n) \Leftrightarrow k_p = \min (m_p, n_p) \max (m_p, n_p) = m_pn_p
$$
故
$$
\gcd(m,n) \operatorname{lcm}(m,n) = mn
$$
(2)
注意到
$$
\gcd(m,n) = \gcd(n \bmod m, m)
$$
$$
\gcd(m,n) \operatorname{lcm}(m,n) = mn
$$
$$
\gcd(n \bmod m, m)\operatorname{lcm}(n \bmod m, m) = (n \bmod m) m
$$
联立等式得
$$
\operatorname{lcm}(m,n) = \frac {n\operatorname{lcm}(n \bmod m, m)} {n \bmod m}
$$
4.3
见答案
4.4
具体考察三种差异：
- 方向相反
- 分子取负
- 分母取负
4.5
由归纳可证：
$$
L^k = \left(\begin{array}{ll}
1 & k \\
0 & 1
\end{array}\right)
$$
$$
R^k = \left(\begin{array}{ll}
1 & 0 \\
k & 1
\end{array}\right)
$$
repo 中的 code/ch4/4.5.cpp 为验证代码。
4.6
$$
a \equiv b \pmod 0 \Leftarrow a = b
$$
因为
$$
a \bmod 0 = a
$$
4.7
根据我在第一章练习题 1.21 中定义的新记号，如果三个死者的编号分别为 $10, k, k+1$，我们有
$$
m \otimes 10 = 10
$$
$$
(10 + m - 1) \otimes 9 = k
$$
$$
(k + m - 1) \otimes 8 = (k + 1) - 1
$$
注意：最后一个等式之所以为 $(k+1)-1$ 是因为正如我们习题 1.21 的解法一样，我们规定了死者编号顺延机制。
经过化简可得：
$$
m \otimes 10 = 10 \Rightarrow m \equiv 0 \pmod {10}
$$
$$
(m-1) \otimes 8 = 8 \Rightarrow m - 1 \equiv 0 \pmod 8
$$
根据上一个式子，$m$ 为偶数，为 10 的倍数，而下面一个式子则暗示了 $m$ 为奇数。矛盾。
4.8
$$
10x + y \equiv x \pmod 3
$$
$$
10x + y \equiv y \pmod 5
$$
经过化简可得第二个同余式恒成立，第一个式子转化为
$$
y \equiv 0 \pmod 3
$$
所以
$$
x = 0, 1
$$
$$
y \equiv 0 \pmod 3
$$
4.9
证明奇数非常容易，因为：
$$
3 \bmod 4 = 3
$$
$$
3 ^ 2 \bmod 4 = 1
$$
由同余乘法法则，
$$
3 ^ {77} \bmod 4 = 3
$$
不难证明：
$$
\frac {3^{77}-1}2 \equiv 1 \pmod 2
$$
接下来，我们找其的一个因数来证明其是合数。
不难得到：
$$
\begin{aligned}
\frac {3^{77}-1} {2} &= \frac {(3-1)(3^{76}+3^{75}+\cdots + 3^0)} {2} \\
&= 3^{76}+3^{75}+\cdots + 3^0 \\
&= (3^0+3^1+\cdots 3^{11})(1 + 3^{11} + 3^{22} + \cdots + 3^{66})
\end{aligned}
$$
4.10
$$
999 = 3^3 \times 37
$$
根据公式
$$
\varphi(999) = 999 \times (1 - \frac 1 3) \times (1 - \frac 1 {37}) = 648
$$
4.11
莫比乌斯函数：
$$
\sum_{d \mid m} \mu (d) = [m = 1]
$$
类推：
$$
\sum_{0 \leq k \leq n} \sigma(k) = [n=0]
$$
不难得出这个函数的通项：
$$
\sigma(n) = \begin{cases}
1 & n = 0 \\ -1 & n = 1 \\ 0 & n > 1
\end{cases}
$$
接下来我们来验证性质。
若 $g(n) = \sum_{0 \leq k \leq n} f(k)$，则
$$
\begin{aligned}
&\sum_{0 \leq k \leq n} \sigma(k) g(n-k) \\
=& \sum_{0 \leq k \leq n} \sigma(n-k) g(k) \\
=& \sum_{0 \leq k \leq n} \sigma(n-k) \sum _{0 \leq j \leq k} f(j) \\
=& \sum_{n-1 \leq k \leq n} \sigma(n-k) \sum _{0 \leq j \leq k} f(j) \\
=& \sum_{0 \leq j \leq n} f(j) + (-1) \sum _{0 \leq j \leq n-1} f(j) \\
=& f(n)
\end{aligned}
$$
若 $f(n) = \sum_{0 \leq k \leq n} \sigma(k) g(n-k)$，则
$$
f(n)=\begin{cases}
g(n)-g(n-1) & n \geq 1 \\ g(0) & n = 0
\end{cases}
$$
故
$$
\sum_{0 \leq k \leq n} f(k) = g(n)
$$
Q.E.D.
4.12
已在 $\mu$ 函数的旁注一文中解答。
4.13
(a)
$$
n_p < 2, \prod_p p^{n_p} = n
$$
(b)
$$
\mu(n) \neq 0
$$
