高中数学扩展/素数/文本

简介

素数（简称素数）是一个自然数，它恰好有两个除数：它本身和数字 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

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

有用的外部资源

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