发表在中国科学院智慧火花文章--利用抽屉原理证明素数无穷多.doc

发表在中国科学院智慧火花栏目文章-利用抽屜原理證明素數無窮多/viewdoc.action?docid=31740王曉明素數無窮多的證明自歐幾里得起，已經有十幾種方法證明，現在我再利用抽屜原理提供一種新的證明方法。抽屜原理又稱鴿巢原理，它是組合數學的一個基本原理，最先是德國數學家狄利克雷明確地提出來的，因此，也稱为狄利克雷原理。 其中一種簡單的表述法為：若有n個籠子和n+1只鴿子，所有的鴿子都被关在鴿籠里，那麼至少有一个籠子有至少2只鴿子。或者另外一種表述法為：若有n+1个籠子和n只鴿子，所有的鴿子都關在鴿籠里，那麼至少有一籠子没有鴿子。證明分為三個板塊： 第一，素数的公式公元前300年古希臘的埃拉斯特尼創造了一種篩法，可以產生任意大的數以内的全部素數： 要得到不大于某個自然數n的所有素数，只要在2n中將不大于素數的倍數全部劃去即可。上述筛法可以總結為：1，如果n是合數，則它有一個因子d滿足1d。2，若自然數n是一個素數，當且僅當它不能被不大于任何素數整除。可以把2的漢字内容等價轉換转换成為英語字母：.(1)其中表示順序素數2，3，5，.。0。若, 則n是一個素數。我們可以把（1）式内容等價轉換同余式組表示：.（2）由於（2）的模,.,兩兩互素，根據孫子定理(中国剩余定理）知，對於給定的,.,，（2）式在.範圍内有唯一解。 範例例如： k=1时，解得n=3，5，7。求得了（3，）區間的全部素數。k=2时，解得n=7，13，19； ，解得n=5，11，17，23。求得了（5，）區間的全部素數。k=3时317,3713,431911,4117,和472329求得了（7，）區間的全部素數。 仿此下去可以一個不漏地求的任何给定數以内的全部素數。由孫子定理知，对于所有可能的值，(1)和(2)式在.範圍内，有（）（）().（）.（3）個解.第二，引理：两个含連續自然數個數相等的區間(間距）篩k次被篩數相差不超過k 埃拉特斯特尼篩法是大家熟知的，現在問：两个連續自然數個數相等或者多個自然數相等的區間同时用k個从小到大不同素數篩，被篩掉的數（或者没有被篩掉的數）不同區間会是一樣的嗎？設n=.，將1至.按 為一組，劃分成.個組（或區間）依次按2,3,5,.顺序篩，篩k次后，任两个含連續自然數個數相等的區間，被篩（或未被篩）數相差不超过k個。即 1， , , . , ,。例如k=4時，n=.=2357=210。 1，35，36 ，70，71，105，106，140，141，175，176，210。證明：根據除法算式定理：“給定正整數a和b，b不等于0，存在唯一整數a和r，（0rb.)，使a=bq+r。” 得知，如果从a中篩bm形數，a個連續自然數中，最多含有q+1個bm形數，r個連續自然數中，最多含有一個bm形數。例如，a=35，b=3，35=3x11+2，35個連續自然數中，最多含有11+1=12个3m形數，例如1-35有11个3m形數，36-70有12个3m形數。現在設某两個區間為A與B，含自然數的个数分别为：|A|与|B|，|A|=|B|，下证明p去篩，两區間被篩pm（m1）形數，個數相差最多不超过1個。由上所述篩法，用顺序素數依次去篩，两區間每次被篩pm形數（或者未被篩數）個數相差最多不超过1個，故篩k次两區間被篩數(或者未被篩數）個數最多不超过k個。證明方法1，设|A|=pm+r，则|B|=pm+r，0rp，即區間A和B中均至少含有m個pm形數，又由於rp，故r個連續自然數中至多有一個pm形數，即被篩pm形數個數相差不超过1個。證明方法2，假若不然，篩k次有两個區間A与B，被篩數相差大於K，比如有K+1個，那麼会出現什麼問題呢？我們問第K+1個是什麼（见图），例如A与B用2和3去筛，如果出现了相差3个，第一个记为2m形，第二个记为3m形，问第三个（ ？）是什么形式？（每一个括号表示一个自然数）。区间A：（+）。（+）；-（-）（-）（-）（-）。（-）；区间B：（+）。（+）（2m)(3m)(?)；-（-）。（-）； |-已经篩過部分-|-未經篩過部分-|。如果第三個（？）是2m或者3m形，顯然与除法算式定理矛盾；如果不是2m或者3m形，它就不應該 “站在” 已經篩過的行列。無論哪一種情況，假设都不能成立。就是说，幾個自然數数相等的區間，用k個不同的篩數去篩，篩完以後，任何两个區間被篩數（或者剩下的數）相差不会超过k個。證毕。 第三，證明如果素數只有有限個，最后一個記為，按照（1）式（2）式寫上，（1）式（2）式就没有小於的解。【1】將1至. 按 为一組，劃分成.個組（或稱為區間） 1，； （）+1，2； .； .（）+1，.。【2】把（1）式（2）式的解數，即（3）式（）（）().（）当做鸽笼。【3】由于假定了（1）式（2）式没有小于的解，第一區間就没有解，（因為 ），如果第一區間無解，根據引理：“两个含連續自然數個數相等的區間篩k次被篩數相差不超k“。其它區間的解數（鴿子）就不会超過k個。还有. 1個區間，總解數（鴿子）不超過（. 1）k個。而：（.1) k（.）k （）（）().（）.（4）【4】 对比（4）式第二项（中间项（.）k ）作为分母，第三项作为分子，一一對應，第三项對應第二项。 （5）除了第一项和第二项分母等于分子外，其他都是每一项分子大于分母。【5】由於鸽笼的數量（）（）().（）是由孫子定理給出的，而装進鴿籠的鴿子.-21) k少于鴿籠，至少有一些鴿籠是空的，这样就违法了孫子定理，與孫子定理矛盾，必然是錯誤的。所以，原先假设最后一个素數是，顯然是錯誤的，素數无穷多个。证毕。2015-03-09 20:171楼 王晓明：首先，感谢审稿老师让这一篇文章发表，并且提出宝贵意见。的确，这个证明过于繁琐，也许还存在一些问题，大家一定会问，为什么搞这些繁琐的东西，难道比欧几里得证明的还好吗？笔者在2001年曾经发表过素数个数问题的三种新证法/link?url=uRqGdSoij1fMq6LLrGIIPf93ZdJoiQPWL1cwLZrPkWQVMFuUxLuDxQoZYKr3IdyX9BdF2MXICGGqoc2JKS3gl_e9cmAZ_YGT8a4DnwyzALK比上面的证明简洁。其实，文章的真正目的是扩展到其他方面。让我们如法炮制：1、 公式利用上面文章的方法，即素数判定法则，可以得到：“若自然数与，都不能被不大于任何素数整除，则与都是素数”。这是因为一个自然数是一个素数，当且仅当它不能被不大于任何素数整除。用数学语言就是存在一组自然数：,.,，使得.(1)其中表示前面k个顺序素数2，3，5，.。这样解得的，若,，则与是一对相差6的孪生素数。我们可以把（1）式内容等价转换成为同余式组表示：由于（2）的模,.,都是素数，因此两两互素，根据孙子定理(中国剩余定理）知，对于给定的e值，（2）在.范围内有唯一解。二、范例例如，k=2时，解得R=7，13； 由于13 6。得知7与7+6,；13与13+6都是相差6的孪生素数。，解得R=5，11，17； 由于176。得知5与5+6,；11与11+6；17与17+6都是相差6的孪生素数。求得了（3，）区间的全部相差6的孪生素数R.,。k=3时=317 和 3713=11 和 411723求得了（5，）区间的全部相差6的孪生素数中的。仿此下去，可以求得任意给定数以内的全部相差6的孪生素数对。根据孙子定理得知，.范围内有：()()()().().（3）个解，因为，对于和来说，0，,是一回事，所以是()()；对于从，.，都是()().()。三、结论推广：相差6的孪生素数猜想就是（1）式（2）式在k值任意大时候都有的解。问题已经转入初等数论范围。四、引理：两个含连续自然数个数相等的区间筛k次被筛数相差不超过k个（参见上面文章第二部分）。五、证明【1】假定相差6的孪生素数对有限，最后一对记为：和或者 和，我们按照（1）式（2）式写上。根据孙子定理，（1）式（2）式的固有解数是（3）式：()()()().().我们把它看成鸽笼（利用抽屉原理）。那么，就没有的解，否则，就是大于的相差6的孪生素数对。也就是没有小于的解，因为。【2】我们把.按照为为一个区间，分为.个区间：1，+1，2,，.，.-（）+1，.。如果第一区间无解，或者任何一个区间无解，还有（.）-1个区间，那么，根据引理，其他区间的解不会超过（.）-1 个，（因为0，,就是筛两次，一共，次），我们把它看成鸽子数。【3】对比：（.）-1（.） 6时，最后一项分子大于分母，即从=7开始，17-2=15 2x7=14=。即从k=7开始，分子()大于分母。其他各项都是分子大于或者等于分母。【4】就是说，如果相差6的孪生素数是有限的，就会造成解数少于（1）（2）式的固有解数，有鸽笼是空的。而固有解数（鸽笼）是孙子定理得到的，孙子定理是说在知，.范围内有：()()()().()个鸽笼，每一个笼子都有一个鸽子。与孙子定理矛盾必然是错误的。证毕。 利用抽屜原理证明特殊类型的素数-孿生素數對 孿生素數的公式利用素數的判定法則，可以得到以下的結論：若自然數與都不能被任何不大於的素數整除，則與都是素數。這是因為一個自然數是素數当且仅当它不能被任何小於等於的素數整除。用數學的語言表示以上的結論，就是：存在一組自然數，使得其中表示從小到大排列時的前k個素數：2，3，5，.。並且滿足這樣解得的自然數如果滿足,則與是一對孿生素數。我們可以把（1）式的內容等價轉換成為同餘方程組表示：由於（2）的模,.,都是素數，因此兩兩互素，根據孫子定理（中國剩餘定理）知，對於給定的，（2）式有唯一一個小於的正整數解。 範例例如k=1時，解得。由於，所以可知與； 與都是孿生素數。這樣就求得了區間里的全部孿生素數對。又比如k=2時，列出方程，解得。由於，所以與；與都是了孿生素數。由於這已經是所有可能的值，所以這樣就求得了區間的全部孿生素數對。k=3時=11,和411729由於這已經是所有可能的值，所以這樣就求得了區間的全部孿生素數對。 仿此下去可以一個不漏地求得任意大的數以內的全部孿生素數對。對於所有可能的值，根據孫子定理，(1)和(2)式在.範圍內，有（）（）().（）.（3）個解。結論推廣孿生素數猜想就是在k值任意大時（1）和（2）式都有小於的解。孪生素数猜想已经转入初等数论范围.引理：參見利用抽屜原理證明素數無窮多证明【1】假定最後一對孿生素數是，我們按照（1）式和（2）式寫上。那麼根據假定，就沒有小於的解。當然也沒有小於的解。【2】將1至.按為一組，劃分成.個組（或區間）1，； （）+1，2；.；.（）+1，.。假定-2之内无解，那么之内无解。【3】我们用反证法证明有解，之内有解就是-2之内有解。【4】，如果第一区间无解，根据引理：“两个含自然数个数相等的区间筛k次被筛数相差不超k“。其它区间的解数就不会超高2k。因为：（1）式（2）式（0;）还有.1个区间，总解数不超过（.1）x2k个。而：（.-2-1) x2k（.-2）x2k 26.分子与分母比例逐渐加大，这是因为每增加一项都是分子大于或者等于分母，经常是大于分母；而（5）式末端也是随着k值增大，商也增大。【6】就是说，如果第一区间1，无解，(或者任何一個區間無解)其他區間的解數不會超過2k個，於是，（1）式（2