具体数学素数旁注

gyro永不抽风

2022 年 03 月 08 日

800次浏览

暂无评论

1181字数

知识技术

注：本节内容为《具体数学》(原书第二版) 第四章数论 4.2 素数的旁注。

P88 关于唯一分解定理的证明

本页下方写道：

我们要证明 $p_{1} = q_{1}$ 。如若不然，我们可以假设 $p_{1} < q_{1}$

突然冒出这句话让人非常不解。这里做出补充。

我们的最终目的是证明所有分解出的素数按照从小到大的顺序排列都是相同的。那么对于

$n = p_{1} \dots p_{m} = q_{1} \dots q_{k}$

$p_{1} \leq \dots \leq p_{m}, q_{1} \leq \dots \leq q_{k}$

若两个分解式中前 $t$ 小个素数都相同，我们不妨设

$n \leftarrow \frac{n}{p_{1} \dots p_{t}} = \frac{n}{q_{1} \dots q_{t}}$

此时将编号重新编号：

$p_{i} \leftarrow p_{i + t}$

$q_{i} \leftarrow q_{i + t}$

然后即可承接书上的论证。

P89 $(4.13)$ 的证明

$m_{p} \leq n_{p} \Leftrightarrow n_{p} - m_{p} \geq 0 \Leftrightarrow \prod_{p} p^{n_{p} - m_{p}} \in Z$

等价于

$n = \prod_{p} p^{n_{p}} = \prod_{p} p^{m_{p}} \prod_{p} p^{n_{p} - m_{p}} = m \prod_{p} p^{n_{p} - m_{p}} = m k, k \in Z$

等价于

$m ∣ n$

P89 $(4.14) (4.15)$ 的证明

试证：

$k = gcd (m, n) \Leftrightarrow k_{p} = min (m_{p}, n_{p})$

$k = lcm (m, n) \Leftrightarrow k_{p} = max (m_{p}, n_{p})$

证明：

根据 $(4.13)$ 可得，条件等价于

$gcd (m, n) ∣ m, n$

$m, n ∣ lcm (m, n)$

所以我们证明了他们分别是公约数和公倍数。接下来使用反证法。不存在一个更大的公约数，假设某一个分量 $k_{p} > min (m_{p}, n_{p})$ ，不失一般性，设 $k_{p} > m_{p}$ ，由于 $(4.13)$ 是等价条件，则根据其的逆否命题会有 $k ∤ m$ ，矛盾。公倍数可有相同方法得到相似结论。故证明了他们分别是最大公约数和最小公倍数。