素数的那些事儿

luyuanhong

素数的那些事儿

作者 | 陆俊

来源 | 数学文化


王元院士 2011 年的科普新作《谈谈素数》

1 引子

近几年开设《初等数论》课程，我总是要抽出一定的时间专门给学生科普一下关于素数的故事。这篇科普文章正是基于这些讲稿整理出来的。

素数是整个数论的灵魂。然而多数学生对素数的了解非常少。很多人不明白：为什么我们要研究素数？素数如何与众不同？素数到底有趣在哪里？素数对数学很重要吗？……如果学生在上完一个学期的数论课后，却仍然对素数茫然无知，那无疑是一种讽刺——这就好比你看完一场戏，不知道主角做了些什么。

写这篇文章的另一目的也是为了给那些依然执着于证明哥德巴赫猜想的民科们做一次扫盲的尝试——尽管他们中的大多数会继续执着下去。然而我们不得不承认这样一个现实：民科们对素数的热情与执着确实远远超过很多数学系的本科生——这多少会让我们这些老师感到沮丧。

2 素数有多少？

我们说一个整数 a 能被另一个整数 b 整除，就是指 a/b 是整数。有时我们也把 b 称作 a 的因子。

一个素数（Prime Number）是指这样一种正整数：除了 1 和它本身之外，其它任何正整数都不可能整除它。我们也可以这么定义素数：它不能写成两个大于 1 的正整数的乘积。有时我们也将素数称作质数。通常我们不承认 1 是素数。这样做的好处下面会介绍。除了 1 和素数之外，其他的正整数统称为合数。

最初的几个素数是 2,3,5,7,11,…。显然 6 不是素数，因为 6＝2×3 ，所有的素数中只有 2 是偶数！这件看似平凡的事，其实很重要。在许多数学研究中，2 和其他素数会对我们所考虑的问题产生不同的影响。你可能会问：为什么我们把这样的数命名为“素数”呢？这实际上来自于素数最基本的结论——算术基本定理：

任何大于 1 的正整数 n 都可以唯一地分解成一些素数的乘积 n＝p1×p2×…×ps ，这里 p1≤p2≤…≤ps 都是素数（允许相同）。

无论如何，素数本身不能再进一步分解成一些更小的正整数乘积，因此它在此意义下是最基本或最本质的数——类似于朴素的原子论——从而命名它们为“素数”或者“质数”。容易看到，假如我们承认 1 是素数，那么算术基本定理就不能保证分解是唯一的了。因为 1 可以写为任意多个自身的乘积。

接下去，一个最自然不过的问题当然是：究竟有多少素数？无限多个还是仅有有限个？这个问题的答案早由欧几里德在两千多年前解决了。他用初等方法巧妙地证明：存在无限多个素数！具体言之，我们假设所有正整数中只有有限个素数 p1,p2,…,pn ，那么可以构造一个正整数 N＝p1p2×…×pn＋1 。

很容易发现，左边的 N 分解成素数乘积的话，不可能包含任何素数 pi ，因此它的分解式中必定含有这些 pi 之外的新素数。这就和我们的假设矛盾！

这个证明包含了富有启发性的思想。事实上，证明本身并没有提供构造出所有素数的具体方法。但是它却能告诉我们素数有无限个！这就是数学中所谓的“存在性证明”：它告诉你某些对象存在，但是却没有具体构造出来。“存在性”是数学哲学中的一个深刻话题，涉及到数学大厦的根基。数学史上曾经关于这类问题有过广泛而激烈的争论，有人反对这种类型的证明，有人却支持它们。这场争论涉及了许多重要的数学家，产生了许多和数学、逻辑、哲学相关的理论。有兴趣的读者可以参考相关书籍，此处不再赘述。

类似欧几里德的证明，你也可以轻松断言：所有被 4 除余数为 3 的素数有无限个！换言之，就是等差数列 3,7,15,19,… 中包含无穷多个素数。这就产生了一个有趣的问题：

一个等差数列 a,a+b,a+2b,…,a+nb,… 中是否包含无限多个素数？

数学家狄利克雷回答了这一问题（狄利克雷定理）：

假如 a 和 b 是互素的（就是说它们不能同时被一个大于 1 的正整数整除），那么答案是肯定的！

不要以为欧几里德的方法可以轻松解决这一问题哦。事实上，除了少数情形之外，这个问题是不可能用它来简单解决的。

如果我们把等差数列换成其他数列，结论会怎样呢？比如考虑以下的数列：

        2,5,10,17,26,…,n^2+1,…

其中是否有无限多个素数呢？让人颇为失望的是，这至今仍是一个未解决的难题。

3 素数是怎么分布的？



4 如何构造素数？

上面的讨论只是介绍了素数在整数中的分布情况，但是我们至今还没有具体构造出这些素数来。一个基本的问题就是：如何构造素数？最原始的办法就是古典筛法。比如我们要找出所有不超过 100 的素数，那么首先将所有从 4＝2^2 开始的偶数全部从这 100 个数中去除掉；接着将所有从 9＝3^2 开始的 3 的倍数全部去除掉；再将所有从 25＝5^2 开始的 5 的倍数全部去除掉……以此类推，最终通过筛选剩下的数恰好就是所有不超过 100 的素数。


数学家群星图；排在最上面的是数论结果及高斯和欧拉等数论先驱



比如 m＝17 是费马素数，因此可以用尺规作图得到正十七边形！要知道，在高斯之前的几百年，有那么多人研究尺规作图问题，但谁也没有想到正十七边形居然可以尺规作图得到。这个结论的重要性在于，它将几何（代数）问题和数论问题这两个看似无关的领域奇妙地结合起来。


美国一家网络安全基金会悬赏超长素数；1 千万位素数的十万美元被加州大学的 Edson Smith 领走。他找到了第 46 个梅森数（见上图）



5 素数和方程



6 素数和代数





其实理想数并不是真正的数，而是一组数的集合。但有趣的是，我们也可以定义这种集合之间的乘法运算，并且定义出类似素数的东西——素理想，最终证明理想数唯一分解定理——算术基本定理的推广。理想数的引入可以说是极为关键的。它使数论的研究观点和方法产生了质的飞跃，促使了代数数论的发展。继库莫的工作之后，戴德金将理想数推广到了更一般情形，从而发展成了系统的理想理论。这一理论是交换代数等学科中的核心内容之一。它不但对数论发展极为重要，而且还深入到其他各个数学领域中，特别是对代数几何等等学科有着重要的影响。

7 素数和函数



8一些题外话

我最早是通过汤涛教授的新浪微博了解《数学文化》的，并立刻被深深吸引住了，成为其忠实粉丝。在这里，我要感谢《数学文化》各位老师给我这次难得的锻炼机会，也要感谢他们在科普传播方面的辛勤劳作，让我们能够看到数学有如此生动有趣的一面。

独木星空谁

在这个图片开始位置好像缺少数字3，完全数6=\(1\over 2\)3(3+1)

luyuanhong

独木星空谁 发表于 2022-7-1 16:56
在这个图片开始位置好像缺少数字3，完全数6=\(1\over 2\)3(3+1)

对，原文中漏写了一个数字 3 。