数的唯一分解定理

任意一个大于0的正整数都能被表示成若干个素数的乘积且表示方法是唯一的。

证明

为了真正地证明分解质因数的方法是唯一的，我们将再次用到反证法。

假设存在某些数，它们有至少两种分解方法。那我我们假设存在一个最小的数$M$，它能用至少两种方法表示成质数的乘积：

$$M = P_1 \times P_2 \times \cdots \times P_r = Q_1 \times Q_2 \times \cdots \times Q_s$$

下面我们将看到，这种假设会推出一个多么荒谬的结果来。

不妨设

$$P_1 \le P_2 \le \cdots \le P_r,Q_1 \le Q_2 \le \cdots \le Q_s$$

显然，$P_1$是不等于$Q_1$的，不然两边同时约掉它，我们就得到一个更小的有两种分解方法的数。

那么不妨设$P_1 < Q_1$，那么我们用$P_1$替换掉等式最右边中的$Q_1$，得到一个比$M$更小的数

$$T = P_1 \times Q_2 \times Q_3 \times \cdots \times Q_s$$

令$M^\prime = M – T$，我们得到$M^\prime$的两种表达：

$$M^\prime = (P_1 \times P_2 \times \cdots P_r) - (P_1 \times Q_2 \times \cdots \times Q_s) = P_1 \times (P_2 \times \cdots \times P_r - Q_2 \times \cdots \times Q_s) \\ M^\prime = (Q_1 \times Q_2 \times \cdots \times Q_s) - (P_1 \times Q_2 \times \cdots \times Q_s) = (Q_1 - P_1) \times Q_2 \times \cdots \times Q_s$$

由于$T$比$M$小，因此$M^\prime$是正整数。

从式中我们立即看到，$P_1$是$M^\prime$的一个质因子。注意到$M^\prime$比$M$小，因此它的质因数分解方式应该是唯一的，可知$P_1$也应该出现在表达式中。

既然$P1$比所有的$Q$都要小，因此它不可能恰好是式中的某个$Q$，于是只可能被包含在因子$(Q_1-P_1)$里。但这就意味着，$(Q_1-P_1)/P_1$除得尽，也就是说$Q_1/P_1-1$是一个整数，这样$Q_1/P_1$也必须得是整数。我们立即看出，$P_1$必须也是$Q_1$的一个因子，这与$Q_1$是质数矛盾了。这说明，我们最初的假设是错误的。