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

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

具体考察三种差异:

  1. 方向相反
  2. 分子取负
  3. 分母取负

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
$$

最后修改:2022 年 03 月 13 日 02 : 56 PM
真的不买杯奶茶嘛....qwq