算数基本定理【Fundamental Theorem of Ar

2021-01-18 本文已影响0人摇摆苏丹

表述

每个整数 $n \geq 2$ 可以唯一分解成素数的乘积 $n = p_1p_2 \cdots p_r$ ，因数的排列顺序不同不视为新的因数分解，且允许因数组合中一个素数出现多次。

证明

算数基本定理可以分解为两个断言：

整数 $n$ 可以以某种方式分解为素数的乘积。
这种因数分解是唯一的。

如果 $n$ 是素数，那么这两个断言显然成立。
如果 $n$ 不是素数，那么分别证明两个断言。

断言1

$n=2,3$ 时， $n$ 是素数，显然断言正确1。 $n=4$ 时， $n=2*2$ ，也正确。现在假设对于直到 $N$ 的每个整数都有断言1成立，也就是每个整数 $n \leq N$ 都可以分解成素数的乘积。对整数 $N+1$ ，如果 $N+1$ 是素数，那么断言正确，如果是合数，设 $N+1 = n_1n_2$ ，显然 $n_1,n_2 \leq N$ ，也就是 $n_1,n_2$ 都可以分解为素数的乘积，那么 $N+1$ 也可以分解为素数的乘积。由归纳法，断言1得证。

断言2

将 $n$ 分解为两种形式的素数乘积，即：
$\begin{array}{c} n = p_1,p_2 \cdots p_r \\ n = q_1,q_2 \cdots q_s \end{array}$
要证明断言2，就要证明这两种形式中的 $p_i,q_j$ 存在一一对应的关系， $r=s$ 也要成立。
首先 $p_1 \mid n = q_1,q_2 \cdots q_s$ ，由素数的整除性质， $p_1$ 必然整除 $q_j$ 中的至少一个。由于 $q_j$ 的排列顺序无关紧要，所以将能被 $p_1$ 整除的那个设为 $q_1$ 。 $p_1,q_1$ 都是素数且 $p_1 \mid q_1$ ，只能 $p_1=q_1$ 。利用这个条件消去等式两边的 $p_1,q_1$ 得到：
$p_2,p_3 \cdots p_r = q_2,q_3 \cdots q_s$
重复上面的逻辑，再次消去 $(p_2,q_2),(p_3,q_3) \cdots (p_{r-1},q_{r-1})$ ，此时得到：
$p_r = q_r,q_{r+1} \cdots q_s$
再消去 $p_r$ ，得到：
$1 = q_{r+1}q_{r+2} \cdots q_s$
上式表示 $q_{j},j \in [r+1,s]$ 都等于1，也就是 $q_{j}$ 都不是素数，这与假设矛盾，因此必有 $r = s$ 。使用 $q_j$ 去消去 $p_i$ ，得到 $p_{s+1},p_{s+2} \cdots p_r = 1$ ，也有相同的结论。
回顾上述过程，发现 $r=s$ ，即 $n$ 的两种因数分解的长度必然相等，又有 $p_1=q_1,p_2=q_2,\cdots ,p_r = q_r$ ，因此两种形式的因数分解等价。断言2得证。

算数基本定理【Fundamental Theorem of Ar

表述

证明

断言1

断言2

猜你喜欢

热点阅读