如何证明素数有无限多个？
关注微信：DuoDaaMath 每天获得更多数学趣文
素数又叫做质数，小学生都知道是什么意思。如果这位小学生对于数学的课外阅读还不错的话，很容易就能证明素数是无限的。
那么，这篇文章岂不是很水？再讲一个小学里总所周知的事？我们哆嗒数学网小编的回答：“是，也不是！”，我们的确在讨论一个简单的数学结论，但却在用不同的数学方法。方法可能涉及抽象代数、拓扑学以及集合论这种大学生都不一定会学习的方法。
文章受到《GÖDEL’S LOST LETTER AND P=NP》博客中文章的启发（WordPress上的博客，一般打不开），想和大家一起分享。
大学生看不懂的高级方法？这么任性？——不是任性，只是忍不住。
第一个方法，从简单的开始讲。小学生能看懂的就是欧几里得的在2000多年前提供的办法了。
假设只有有有限多个素数。设$p_1,p_2,\cdots,p_m$是全部$m$个素数，令$p=p_1p_2\cdots p_m+1$。则$p_1,p_2,\cdots,p_m$都不是$p$的素因数。所以$p$是有一个与$p_1,p_2,\cdots,p_m$都不同的素数。矛盾。
把欧几里得的这个办法做一些小修改，就是令前面的$p$为$p_1p_2\cdots p_m-1$，在做一些程度不大的改变，也可以证明素数是无限的。利用这个改变后的思想可以证明下面一个简单的命题——“有无穷多个型如$4n-1$的素数”。 证明过程是这样的，如果只有有限个$p_1,p_2,\cdots,p_m$互素，令$N=4p_1p_2\cdots p_m-1$。下面的讨论和前面差不多，首先$p_1,p_2,\cdots,p_m$都不是$N$的素因数，所以$N$的素因数只能是型如“$4n+1$”，这样两边除以$4$的余数不一样，矛盾。
第二种办法，用到排列组合的知识，高中生能看懂，叫做数数法。考虑一个正整数$x$,那么不大于$x$的正整数取值方式有$x$种。把每个$2$与$x$之间的正整数唯一地写成$r^2s$形式，其中$s$的素因数都不超过$1$次的。那么$r\le\sqrt{x}$，就是说$r$取值方式最多$[\sqrt{x}]$种，如果只有$m$个素数，那么$s$的取值方式最多$2^m$。于是$[\sqrt{x}]2^m\ge x$。当$x$足够大时，不等式不可能成立。
热身完毕，进入高级模式。
方法三，抽象代数办法。如果$\mathbb{Z}$只有有限个素理想，那么单扩张$\mathbb{Z}[\sqrt{-5}]$是唯一分解整环。但$6=2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5})$，矛盾。注意$1\pm\sqrt{-5}$在这个环下不可分解，不是很显然的，了解抽象代数的读者可以试试证明它。
方法四，再来一个拓扑学的办法。在整数集合中，每个从$-\infty$走到$+\infty$的等差数列中所有的数做成一个集合。用这些集合做基，可以生成一个拓扑。令$A_p=p\mathbb{Z}$那么$A_p$不仅是开集，它还是闭集，这是因为$\mathbb{Z}\setminus A_p=\bigcup\limits_{i=1}^{p-1}\{pn+i~:~n\in\mathbb{Z}\}$是一簇开集的并，即开集，于是补集是闭集。如果只有有限个素数得到$P=\bigcup\limits_{p}A_p$，并集跑遍素数时，得到$P$是闭集。但$\mathbb{Z}\setminus P=\{-1,1\}$不是开集，矛盾。
方法五，集合论来了。在整数集合中，还是用每个从$-\infty$走到$+\infty$的等差数列中所有的数做成一个集合。用这些集合做成集簇$\mathcal{A}$。$\mathcal{A}'=\mathcal{A}\cup\{\emptyset\}$显然对有限交运算封闭，而且用方法四中的办法可以证明，对$A\in\mathcal{A}$有$A^c$可以写成有限个$\mathcal{A}$中成员的并。而且对于有限个$A_1,A_2,\cdots,A_m\in \mathcal{A}$，他们的并的补集不可能是非空有限集。这是因为$F=\left(\bigcup\limits_{i=1}^m A_i\right)^c=\bigcap\limits_{i=1}^m A_i^c$，而每个$A_i$是有限个$\mathcal{A}$中元素的并。再利用一下交并的分配率对有限交的封闭性，得到结果是$F$是有限个$\mathcal{A}'$的并，所以要么是无限集合，要么$\emptyset$。这样，如果素数是有限集，令$F=\{-1,1\}$而$A_p=p\mathbb{Z}$，其中$p$跑遍素数得到矛盾。
关注微信：DuoDaaMath 每天获得更多数学趣文
评论已关闭