高中数学扩展/素数

高中数学扩展

---

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

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

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

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。

由于计算机非常擅长进行算术运算，我们可以通过简单地指示计算机用 2、3、5、7 ... 依次除以x来计算出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

九能被 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 形式的素数被称为 梅森素数，以法国僧侣兼业余数学家命名。

有用的外部资源

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

>> 下一节： 模算术