算数基本定理及其推论证明

算术基本定理：每个自然数有且仅有一种被写为素数乘积的方式（不考虑先后顺序）。

即合数分解质因数形式是唯一的。

推论：如果一个素数 $p$ 是乘积 $ab$ 的因子，则 $p$ 必须或是 $a$ 的因子，或是 $b$ 的因子。

这个推论是“显而易见”的，但是直接证明却有难度，很适合使用反证法。

证：

假设

$$\begin{aligned} & p \notin \{x | \; x \;{\small|}\; a \; \cup \; x \;{\small|}\; b\} \\ & a = \prod_{i=1}^m{p_i}, \quad b = \prod_{j=1}^n{q_j} \quad (\forall p_i \neq p, \quad \forall q_j \neq p) \\ & ab = \prod_{i=1}^m{p_i} \cdot \prod_{j=1}^n{q_j} \\ & \because p\;|\;ab \\ & \therefore \exists \; t \; 使 \; ab=pt, 设 \; t = \prod_{k=1}^c{r_k} \; 则 \; ab = p\cdot\prod_{k=1}^c{r_k} \end{aligned}$$

这说明，$ab$ 有两种质因数分解形式，与算术基本定理矛盾，得证。