康爷的博客

为什么要讲这个话题，因为既然取名叫IT VS 数学，自然要谈谈数学，而要谈数学，要谈数学科普，我最喜欢谈的就是这个命题。原因？这个比较好玩！呵呵

学到质数，或者称为素数，应该是小学，初中的事。质数要求很严格，要求没有约数（除了自身和1），所以不是很多的。我自己读初中时，100以内的质数是需要背全的，可见不多，现背如下，考验考验自己的记忆呵呵：

2，3，5，7，11，13，17，19，23，29，31，37，41，43，47， 53，59，61，67，71，73，79，83，89，97

可以看见，越到后面质数越来越少，一个很自然的问题：质数有多少个？？

其实不自然啦，因为我问过很多人这个问题，没有人想到过这个问题，当然从这个角度可以写一篇批判应试教育的文章。。。我不高兴写了

在我问完这个问题之后，没人回答得出（废话，我当然是找回答不出的人问的～）。原因当然有二，一是这些被问者没听过解答，二就是这个问题并不简单。

公布答案：质数有无穷多个！！！

为什么？

本以为是个很难的题目，可是，两千多年前，有一位中国观众十分熟悉的人物叫欧几里德，把这个问题给解决了，而且解决得如此让人无话可说，感叹数学之妙，数论之美。

不过，千万别以为欧几里德画了两个圆把这个问题给解决了，如此的话欧几里德就是“古代几何数论”的开山鼻祖了。可是他现在是“欧氏几何”的鼻祖，当然还有一个和此有关的重要内容，也是搞计算机的同学们很早就会遇到的一个内容：欧几里德辗转相除法。

现证明如下：（这个证明我也自己写一遍～）

命题：质数有无穷多个。

证明：用反证法。假设质数只有有限多个，那么设质数共有n个，且分别是p1=2,p2=3,p3,p4…,pn。

考察p=p1*p2*p3*…*pn+1，显然p>pk(k=1,2,3,..,n)(理由：p>pk+1>pk)

由于质数只有n个，且p>pn，所以p不是质数。

然而，p又无法被任何一个质数pk整除（因为pk|p1*p2*..*pn，但pk不能整除1，所以pk不能整除p1*p2*..*+1=p），

于是p是质数，矛盾！

故原命题成立，即素数有无穷多个。   #

多说无益了，只有一句，欧几里德真伟大~