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

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

本页下方写道：

我们要证明 $p_1 = q_1$。如若不然，我们可以假设 $p_1 < q_1$

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

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

$$
n = p_1 \cdots p_m = q_1 \cdots q_k
$$

$$
p_1 \leq \cdots \leq p_m, q_1 \leq \cdots \leq q_k
$$

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

$$
n \leftarrow \frac {n} {p_1 \cdots p_t} = \frac {n} {q_1 \cdots 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 \mathbb 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} = mk, k \in \mathbb Z
$$

等价于

$$
m \mid n
$$

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

试证：

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

证明：

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

$$
\gcd (m,n) \mid m, n
$$

$$
m, n \mid \operatorname{lcm} (m,n)
$$

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