因数分解与算术基本定理

文章目录

1 素数整除性质
2 算术基本定理
3 因数分解的方法
4 参考资料

1 素数整除性质

我们知道，素数 $p$ （ $\ge 2$ ）是正因数仅有 $1$ 和 $p$ 的数，不是素数的整数 $m$ （ $m\ge 2$ ）叫做合数：
$素数:2,3,5,7,11,13,17,19,23,29,31,\cdots \\ 合数:4,6,8,9,10,12,14,15,16,18,20,\cdots$
下面这条引理是很重要的，但并不显然。

引理：令 $p$ 是素数，假设 $p$ 整除乘积 $a b$ ，则 $p$ 整除 $a$ 或 $p$ 整除 $b$ 。下面来证明这条引理。

证明：
如果 $p$ 整除 $a$ ，则证明完毕。现在假设 $p$ 不整除 $a$ 。考虑 $g c d (a, p)$ ，既然它整除 $p$ 那么它就是 $1$ 或 $p$ ，又因为 $p$ 不整除 $a$ ，所以 $g c d (a, p) = 1$ 。根据线性方程定理，我们可以求得方程：
$p x + a y = 1$
的整数解 $x, y$ ，现在方程两边同时乘以 $b$ 得到：
$p b x + a b y = b$
显然 $p$ 整除 $p b x$ ，又因为我们已知 $p$ 整除 $a b y$ ，所以 $p$ 整除 $b$ 。

进一步，我们可以将这条引理推广到多个因数的乘积形式，就得到了下面这条定理。

定理（素数整除性质）：假设素数 $p$ 整除乘积 $a_1a_2\cdots a_r$ ，则 $p$ 整除 $a_1,a_2,\cdots ,a_r$ 中至少一个因数。

利用上述引理可以很容易地证明这条定理。

2 算术基本定理

算术基本定理：每个整数 $n\ge 2$ 可唯一分解成素数乘积： $n=p_1p_2\cdots p_r$ 。

这里分解出来的素数乘积并非指不同的素数，例如 $300 = 2 * 2 * 3 * 5 * 5$ ，并且不认为因数重排是新的因数分解。下面来证明该定理。

证明：
首先证明数 $n$ 可以以某种方式分解成素数乘积，利用数学归纳法。首先 $2 = 2, 3 = 3, 4 = 2 * 2$ 成立，假设对于 $n\le N$ 都成立，我们需要验证 $N + 1$ 时结论成立。

因此就有两种可能性，首先如果 $N + 1$ 是素数，那么它本身就已经分解成素数；其次 $N + 1$ 是合数，这表明 $N + 1$ 可分解为 $n_1n_2$ （ $2\le n_1,n_2 \le N$ ），根据假设， $n_1,n_2$ 都可以分解成素数的乘积：
$n_1 = p_1p_2\cdots p_r\\ n_2=q_1q_2\cdots q_r$
因此 $N+1=p_1p_2\cdots p_rq_1q_2\cdots q_r$ ，所以 $N + 1$ 也可以分解成素数的乘积，得证。

接下来证明唯一性，即只有一种这样的因数分解。我们假设 $n$ 能够被分解为两种形式的素数乘积：
$p_1p_2\cdots p_r\\ n=q_1q_2\cdots q_s$

首先， $p_1|n$ ，所以 $p_1|q_1q_2\cdots q_s$ ，根据上面提到的素数整除性质， $p_1$ 整除至少一个 $q_i$ ，不妨让它等于 $q_1$ ，又因为 $q_1$ 也是素数，因此 $p_1=q_1$ ，这样我们就可以同时消掉 $p_1,q_1$ 得：
$p_2\cdots p_r=q_2\cdots q_s$
同理我们可以消去 $p_2,p_3,\cdots$ ，如果左边的 $p$ 先被消去，那么左边就是 $1$ ，因此右边也应该是 $1$ ，所以这两个分解的因数个数是相同的即 $r = s$ ，并且重排一个序列可以得到另外一个序列。所以唯一性也得到了证明。

3 因数分解的方法

当 $n$ 很小时，我们可以挨个试，但是 $n$ 比较大的时候，因数分解就很困难了。一种方法是用素数 $2,3,5,7,\cdots$ 去除 $n$ ，知道找到一个因数，再对剩余部分继续尝试。

如果 $n$ 本身不是素数，则必有整除 $n$ 的素数 $p\le \sqrt n$ 。因为如果 $p$ 是整除 $n$ 的最小素数，则 $n=pm,m\ge p$ ，从而 $n=pm\ge p^2$ ，两边同时开平方就可以得到这个结论。这个结论给出了将任何整数 $n$ 分解成素数乘积的方法：

用小于等于 $\sqrt n$ 的每个数（或正好每个素数）试除它。如果没有求得整除 $n$ 的整数，则 $n$ 本身是素数，否则求得的第一个因数是素数 $p$ ，再对 $m = n / p$ 重复这个过程。

这个过程效率非常低，但是对适当大小的数，在计算机上工作得还是很好的。但是对非常非常大的数，要计算出因数分解，就需要很长时间了。因此就产生了两个紧密相关的问题：

如何分辨已知数 $n$ 是素数还是合数？
如果 $n$ 是合数，如何将它分解成素数的乘积？

第一个问题更容易回答，即便求不出来大数的因数，我们以可以知道它是否是合数。用类似的方式我们可以求得很大的素数 $p, q$ 这样如果给定一个 $n = p q$ ，就不可能通过分解 $n$ 来获得数 $p$ 与 $q$ 。这个事实也是用数论建立高度安全密码的关键所在。

4 参考资料

《数论概论》第四版 P31-P35

今天的文章因数分解与算术基本定理分享到此就结束了，感谢您的阅读。