高中数学扩展/素数

高中数学扩展

---

补充章节 — 素数和模算术 — 逻辑

数学证明 — 集合论和无限过程 — 计数和生成函数 — 离散概率

矩阵 — 进一步的模算术 — 数学规划 — 马尔可夫链

HSME
内容
素数
模算术
问题与项目
习题集
项目
解决方案
练习题答案
习题集答案
杂项
定义表
完整版
PDF 版本

介绍

素数（简称素数）是一个自然数，它恰好有两个因数：它本身和数字 1。由于 1 只有一个因数——它本身——我们不认为它是一个素数，而是一个单位。因此，2 是第一个素数，3 是下一个素数，但 4 不是素数，因为 4 除以 2 等于 2 且无余数。我们已经证明 4 有三个因数：1、2 和 4。具有两个以上因数的数字称为合数。

前 20 个素数是 2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67 和 71。

质数是数学家们永无止境的迷恋源泉。一些关于质数的问题非常难，即使一些最杰出的数学家数十年来的研究也未能解决。其中一个问题是哥德巴赫猜想，它提出所有大于 3 的偶数都可以表示为两个质数之和。没有人能够证明它真或假。

本章将介绍质数的一些基本性质及其与一个称为模算术的数学领域之间的联系。

质数的几何意义

上面三幅图展示了将 12 块方形地砖拼成矩形的不同方式。下面三幅图展示了 7 不能被 2 整除（左图），也不能被 3 整除（右图）。

给定 12 块方形地砖，我们能否以不止一种方式将它们拼成矩形形状？当然可以，这是因为

${\begin{matrix}12&=&12\times 1\\&=&6\times 2\\&=&4\times 3\\\end{matrix}}$

我们不区分 2×6 和 6×2，因为它们本质上是等价的排列。

但数字 7 呢？你能以不止一种方式将 7 块方形地砖排列成矩形形状吗？答案是不，因为 7 是一个质数。

算术基本定理

一个 **定理** 是一个非显而易见的数学事实。定理必须被证明；一个被普遍认为是真实的命题，但没有证明，被称为 **猜想** 或 **假设**。

有了这些定义，算术基本定理简单地说：

任何自然数（除了 1）都可以唯一地表示为质数的乘积。

例如

$12=2\times 2\times 3\,\!$

重新排列乘法顺序不视为数字的不同表示，因此没有其他方法可以将 12 表示为质数的乘积。

还有一些例子

${\begin{matrix}99&=&3&\times &3&\times &11\\52&=&2&\times &2&\times &13\\17&=&17&\end{matrix}}$

可以很容易地看出，合数有多个质因数（重复的质因数多次计数）。

为什么？

记住算术基本定理的定义，为什么数字 1 不被视为质数？

因式分解

我们从算术基本定理知道，任何整数都可以表示为质数的乘积。百万美元的问题是：给定一个数字 x，是否存在一种 简单 的方法来找到 x 的所有质因数？

如果 x 是一个小的数字，那么它很简单。例如 90 = 2 × 3 × 3 × 5。但如果 x 很大呢？例如 x = 4539？大多数人无法在脑中将 4539 分解成质数。但是计算机可以吗？是的，计算机可以相当快地将 4539 分解成质数。我们有 4539 = 3 × 17 × 89。

由于计算机非常擅长算术运算，我们可以通过简单地指示计算机依次将 x 除以 2、3、5、7 ... 等等来计算出 x 的所有因数。

所以，存在一种 简单 的方法将数字分解成质因数。只需应用上面描述的方法即可。然而，该方法对于大数字来说太慢了：尝试将一个有数千位数字的数字分解成质因数将花费的时间超过当前宇宙的年龄。但有没有一种 快速 的方法？或者更准确地说，有没有一种 高效 的方法？可能存在，但还没有人找到。如今一些最广泛使用的加密方案（如 RSA）利用了我们无法快速将大数字分解成质因数这一事实。如果找到了这种方法，许多互联网交易将变得不安全。

考虑以下三个分解方法的实际例子。

例子 1

$x=21$

${\frac {x}{2}}=10.5$ 不是一个整数，所以 2 不是 21 的因数

${\frac {x}{3}}=7$ 因此 3 和 7 是 21 的因数。

例子 2

$x=153$

${\frac {x}{2}}=76.5$ 因此 2 不是 153 的因数

${\frac {x}{3}}=51$ 因此 3 和 51 是 153 的因数

${\frac {51}{3}}=17$ 因此 3 和 17 是 153 的因数

很明显，3、9、17 和 51 是 153 的因数。153 的质因数是 3、3 和 17（3×3×17 = 153）

例子 3

${\frac {2057}{2}}=1028.5$

$\cdots$

${\frac {2057}{11}}=187$

${\frac {187}{11}}=17$

因此，11、11 和 17 是 2057 的质因数。

练习

对下面给定的数字进行因式分解

1

13=

2

26=

3

59=

4

82=

5

101=

6

121=

7 如果花费的时间太长，就放弃。有一个快速的方法。

2187=

有趣的事实——它是质数吗？

有趣的是，借助计算机，有一种有效的方法可以以 100% 的准确率确定一个数字是否为质数。

2、5 和 3

质数 2、5 和 3 在因式分解中占有特殊地位。首先，所有偶数都有 2 作为其质因数之一。其次，所有最后一位数字为 0 或 5 的数字都可以被 5 整除。

第三种情况，3 是一个质因数，是本节的重点。关键问题是：是否有简单的方法来判断一个数字是否具有 3 作为其质因数之一？

定理——可被 3 整除

一个数可被 3 整除当且仅当其各位数字之和可被 3 整除。

例如，272 不可被 3 整除，因为 2 + 7 + 2 = 11，而 11 不可被 3 整除。

945 可被 3 整除，因为 9 + 4 + 5 = 18。而 18 可被 3 整除。事实上，945 / 3 = 315。

123456789 可被 3 整除吗？

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = (1 + 9) × 9 / 2 = 45

4 + 5 = 9

9 可被 3 整除，因此 45 可被 3 整除，因此 123456789 可被 3 整除！

该定理的妙处在于其递归性。一个数可被 3 整除当且仅当其各位数字之和可被 3 整除。我们如何知道其各位数字之和是否可被 3 整除？再次应用该定理！

信息——递归

一位著名的计算机科学家曾经说过“迭代是人的行为，递归是神的行为”。但递归是什么意思呢？在此之前，迭代是什么意思呢？
“迭代”只是意味着一遍又一遍地做同一件事，而计算机非常擅长这一点。数学中迭代的一个例子是指数运算，例如 xⁿ 表示 x 乘以 x 乘以 x 乘以 x......n 次。这是一个迭代的例子。

经济地（就心理资源而言）思考迭代，通过用自身来定义问题，就是“递归”。为了递归地表示 xⁿ，我们写

$x^{n}=1$ 如果n 等于 0。

$x^{n}=x\times x^{n-1}$ 如果n > 0

9⁹ 是多少？它是 9 乘以 9 ⁸。但是，9⁸ 是 9 乘以 9⁷。以这种方式重复就是一个递归的例子。

练习

对于问题 1-3，进行因式分解

1

45=

2

4050=

3

2187=

4 证明可被 3 整除定理对于任何三位数都适用。

（在纸上完成）

5 一个数可被 9 整除当且仅当其各位数字之和可被 9 整除。

	正确
	错误

确定问题 6-9 中的数字是否可被 9 整除。

6 89

	是
	否

7 558

	是
	否

8 51858

	是
	否

9 41857

	是
	否

寻找质数

质数筛是一种相对有效的寻找小于或等于指定数字的所有质数的方法。要找到所有小于或等于 50 的质数，我们执行以下操作

首先，我们将 1 到 50 的数字按如下表的方式写出来

${\begin{matrix}1&2&3&4&5&6&7&8&9&10\\11&12&13&14&15&16&17&18&19&20\\21&22&23&24&25&26&27&28&29&30\\31&32&33&34&35&36&37&38&39&40\\41&42&43&44&45&46&47&48&49&50\\\end{matrix}}$

划掉 1，因为它不是质数。

${\begin{matrix}X&2&3&4&5&6&7&8&9&10\\11&12&13&14&15&16&17&18&19&20\\21&22&23&24&25&26&27&28&29&30\\31&32&33&34&35&36&37&38&39&40\\41&42&43&44&45&46&47&48&49&50\\\end{matrix}}$

现在 2 是表中没有划掉的最小数字。我们将 2 标记为质数，并划掉所有 2 的倍数，即 4、6、8、10 …

${\begin{matrix}X&2_{p}&3&X&5&X&7&X&9&X\\11&X&13&X&15&X&17&X&19&X\\21&X&23&X&25&X&27&X&29&X\\31&X&33&X&35&X&37&X&39&X\\41&X&43&X&45&X&47&X&49&X\\\end{matrix}}$

现在 3 是没有标记的最小数字。我们将 3 标记为质数，并划掉所有 3 的倍数，即 6、9、12、15 …

${\begin{matrix}X&2_{p}&3_{p}&X&5&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&25&X&X&X&29&X\\31&X&X&X&35&X&37&X&X&X\\41&X&43&X&X&X&47&X&49&X\\\end{matrix}}$

继续这种方法找到所有质数。你什么时候知道你已经找到了 50 以内的所有质数？注意这个算法叫做 埃拉托色尼筛法

练习

1. $${\begin{matrix}X&2&3&X&5&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&X&X&X&X&29&X\\31&X&X&X&X&X&37&X&X&X\\41&X&43&X&X&X&47&X&X&X\\\end{matrix}}$$上面表格已经应用了素数筛法。注意，在2和5下方直接的每个数字都被划掉了。构造一个从1到60的数字矩形网格，使得在对它应用素数筛法之后，所有在2和5下方直接的数字都被划掉。网格的宽度是多少？
2. 找到200以下的所有素数。
3. 找到200以下所有能被3整除的数字。你改变了网格的宽度吗？

无限多个素数

为了回答问题“最大的素数是多少？”，让我们先回答“最大的自然数是多少？” 如果有人告诉你 $10^{10}$ 是最大的自然数，你可以立即证明他们错了，因为你可以告诉他们 $10^{10}+1$ 是一个更大的自然数。你可以用任何其他自然数 $n$ 代替 $10^{10}$，你的论证仍然有效。这意味着没有所谓的“最大的自然数”。（有些人可能会说“无穷大”是最大的自然数。但是，无穷大不是自然数，而只是一个数学概念。）

古希腊数学家 欧几里得，对素数无穷性的证明如下：

素数无穷性的证明

让我们先假设

素数的数量是有限的

因此

一定存在一个比所有其他素数都大的素数，

我们将这个素数称为 *n*。我们现在将证明上面这两个假设会导致矛盾，因此存在无限多个素数。

将所有素数的乘积相乘得到一个数字 *x*。因此

$x=2\times 3\times 5\times \ldots \times n\!$

然后，令 *y* 等于 *x* 加 1

$y=x+1\!$

现在可以得出结论，*y* 不能被任何小于等于 *n* 的素数整除，因为 *y* 与每个素数的倍数只差 1。由于 *y* 不能被任何素数整除，因此 *y* 必须是素数，或者它的素数因子必须都大于 *n*，这与最初的假设（*n* 是最大的素数）相矛盾！因此，必须宣布最初的假设是错误的，并且存在无限多个素数。

趣闻 — 已知最大的素数

已知最大的素数是 2^82,589,933-1。它有惊人的 24,862,048 位数！形如 2ⁿ-1 的素数被称为 梅森素数，以法国僧侣/业余数学家命名。

有用的外部资源

• "素数页面。素数研究、记录和资源"

>> 下一节： 模运算