你在这里

如何证明素数有无限多个?

 

关注微信:DuoDaaMath 每天获得更多数学趣文

新浪微博:http://weibo.com/duodaa

 

素数又叫做质数,小学生都知道是什么意思。如果这位小学生对于数学的课外阅读还不错的话,很容易就能证明素数是无限的。

那么,这篇文章岂不是很水?再讲一个小学里总所周知的事?我们哆嗒数学网小编的回答:“是,也不是!”,我们的确在讨论一个简单的数学结论,但却在用不同的数学方法。方法可能涉及抽象代数、拓扑学以及集合论这种大学生都不一定会学习的方法。

文章受到《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 每天获得更多数学趣文

新浪微博:http://weibo.com/duodaa