素数与算术基本定理

摘要

本课研究素数，即自然数乘法的原子。本课证明每个大于 $1$ 的自然数都有素因数，介绍埃拉托斯特尼筛法以及为什么筛到平方根就够了，并跟随欧几里得证明素数有无穷多个。随后证明欧几里得引理，即整除一个乘积的素数必整除它的某个因数，并借助它证明算术基本定理：每个大于 $1$ 的自然数都能以唯一的方式写成素数的乘积。由素因数分解可以推出一个自然数的因数个数、完全平方数的刻画，以及每个不是完全平方数的自然数的平方根的无理性。

学习目标

区分素数与合数，并证明每个大于 $1$ 的自然数都有素因数。
应用埃拉托斯特尼筛法，并说明为什么只需划去不超过上限的平方根的那些素数的倍数。
证明素数有无穷多个、欧几里得引理以及素因数分解的存在性与唯一性。
利用素因数分解计数和列举因数、识别完全平方数，并证明平方根的无理性。

素数与合数

在关于整除与带余除法的课中已经看到，每个自然数 $n$ 都能被 $1$ 和它自身整除。有些自然数除了这两个以外没有别的因数；它们是零件，所有其他自然数都由它们通过乘法组成。

定义（素数）。自然数 $p$ 称为素数，如果 $p > 1$ 并且它的因数只有 $1$ 和 $p$ 。不是素数的自然数 $n > 1$ 称为合数：它可以写成 $n = ab$ ，其中 $1 < a < n$ 且 $1 < b < n$ 。数 $1$ 既不是素数也不是合数。

小于 $50$ 的素数有以下十五个：

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

$2$ 是唯一的偶素数，因为其他每个偶数都有因数 $2$ ，它既不同于 $1$ ，也不同于该数本身。排除 $1$ 并非定义的任性之举：如果 $1$ 是素数，素因数分解就不再唯一，因为 $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3$ ，本课的核心定理就不得不带着一个例外来陈述。

良序原理

本课的证明依赖于归纳原理的一种形式，它对于关于因数的推理特别方便：良序原理，即每个非空的自然数集合都有最小元。它已在关于求和、数列与归纳法的课中由强归纳法推出，这里直接使用，不再重复其证明。

每个大于 1 的自然数都有素因数

本课的第一个结果保证，没有任何大于 $1$ 的自然数能逃脱素数：总有一个素数整除它，而且可以在它最小的那些因数中找到。

命题大于 1 的最小因数是素数

每个自然数 $n > 1$ 都有素因数： $n$ 的大于 $1$ 的最小因数是素数。此外，若 $n$ 是合数，则它的最小素因数 $p$ 满足 $p^2 \leq n$ 。图在数轴上标出 $n = 91 = 7 \cdot 13$ 的因数。

证明

$\dato{D}{D = \{ d \in \mathbb{N} : d \mid n \wedge d > 1 \}}, \quad n \in D, \quad m = \min D$
$n$ 的大于 $1$ 的因数组成的集合非空，因为它包含 $n$ 本身；由良序原理，它有最小元 $m$ 。
$a \mid m \wedge m \mid n \rightarrow \resaltar{a \in D}, \quad \resaltar{a < m}$
如果 $m$ 是合数， $m = ab$ ，其中 $1 < a < m$ ，那么因数 $a$ 整除 $m$ ，并且由整除的传递性，它也整除 $n$ ：它将是 $D$ 中小于 $m$ 的元素，与 $m$ 的选取矛盾。所以 $m$ 是素数。
$\dato{k}{n = pk, \quad k \in D}$
现在设 $n$ 是合数，并设 $p$ 是它的最小素因数，也就是 $D$ 的最小元。写出 $n = pk$ ；由于 $n$ 不是素数， $k \neq 1$ ，而且 $k$ 也整除 $n$ 。
$p^2 = p \cdot p \leq \resaltar{p \cdot k} = n$
由 $p$ 的最小性得 $k \geq p$ ，再由乘法的单调性得到这个上界。

因此，要判断一个自然数 $n$ 是否为素数，只需逐一试验素数 $p$ （满足 $p^2 \leq n$ 者）：如果其中没有一个整除它， $n$ 就是素数。例如，对于 $221$ ，只需试验到 $13$ 为止的素数，因为 $17^2 = 289 > 221$ ：它不能被 $2$ 、 $3$ 、 $5$ 、 $7$ 或 $11$ 整除，但能被 $13$ 整除，并且 $221 = 13 \cdot 17$ 。相反， $211$ 不能被素数 $2$ 、 $3$ 、 $5$ 、 $7$ 、 $11$ 和 $13$ 中的任何一个整除，又因为 $17^2 = 289 > 211$ ，所以 $211$ 是素数。