1、如何證明形如4n3的素?cái)?shù)有無(wú)限多個(gè) 篇一：證明形如4n+3的素?cái)?shù)有無(wú)限多個(gè) 四、證明題（每小題10分，3題共30分） 1.證明：形如4n+3（n為非負(fù)整數(shù)）的素?cái)?shù)有無(wú)限多個(gè). 證明：用反證法 若形如4n3的素?cái)?shù)為有限個(gè)，設(shè)為p1,p2,pk.(整個(gè)證明的思想是用反正法，先設(shè)形如4n+3的素 數(shù)只有有限個(gè)，設(shè)為p1,p2,pk，再找到4n+3形式 的數(shù)p,并且這個(gè)p是不等于p1,p2,pk的，這樣就與 我們假設(shè)的有限個(gè)就矛盾了) 令q4p1p2pk14(p1p2pk1)3，（現(xiàn)在構(gòu)造一個(gè)數(shù)q，通過(guò)變形我們知道q也是4n+3 形式的數(shù)，顯然qpi,i1,2,.k（若相等則有 (4p1p2pi1pi

2、1pk1)pi1，這不可能），若q已經(jīng)為 素?cái)?shù)，就找到了不等于p1,p2,pk的素?cái)?shù)q，定理已 經(jīng)得證，若q不是素?cái)?shù)，我們考慮它的素因數(shù)，在 下面的步驟） 顯然pi都除不盡q.（反證法，若能除盡，即piq，而由上面可知14p1p2pkq，則有pi1，矛盾） 若q為素?cái)?shù)，而qpi，i1,2,.k，定理已經(jīng)得證.（這個(gè)結(jié)論上面的注已經(jīng)說(shuō)明） 現(xiàn)在考察q不是素?cái)?shù)，那么它必有素因數(shù) （一個(gè)數(shù)能分解為若干素?cái)?shù)的乘積） (4l1)(4m1)4(4lmlm)14u1，（此式子說(shuō)明4n+1形式的乘積還是4n+1的形式） 而q一定不能全是4n1形式素因數(shù)， 一定還有4n3形式的素因數(shù)p， （因?yàn)閝也是4n+3的

3、形式，若全是4n+1的形式， 它們的乘積得不到4n+3的形式，故一定還有 4n3 形式素因數(shù)p. 由假設(shè)知q是奇數(shù)，它的因 數(shù)肯定都是奇數(shù)，所以它的因數(shù)要么是4n+1的形 式，要么是4n+3的形式，不可能是4n+2與4n+4 的形式（因?yàn)檫@兩個(gè)還是偶數(shù)） 且不是p1,p2,pk中的一個(gè)，與假設(shè)矛盾. （前面已經(jīng)證明pi都除不盡q，而p是q的因數(shù)， 因此p能整除q，故p不是p1,p2,pk中的一個(gè)） 故形如4n3的素?cái)?shù)有無(wú)限多.（一開始我們假設(shè)的是有限個(gè)，k個(gè)，而現(xiàn)在我們 找到了不等于p1,p2,pk的其它的4n+3形式的素 數(shù)p，順環(huán)往復(fù)，這說(shuō)明有限個(gè)的假設(shè)不正確， 故形如4n+3的素?cái)?shù)有無(wú)限

4、多個(gè)） 注：主要步驟就是黑字的部分，后面的彩色的字是我做的注解，做題目的時(shí)候可以不寫。 摘要：有關(guān)于素?cái)?shù)的個(gè)數(shù)是無(wú)窮多個(gè)的定理有許多的證明方法，最早的證明要見(jiàn)于歐幾里德的名著幾何原本第九篇的命題20中：素?cái)?shù)的數(shù)目比以往任何指定的數(shù)目都要多，即素?cái)?shù)有無(wú)窮多個(gè).本文在總結(jié)前人證明的基礎(chǔ)上用數(shù)學(xué)歸納法再次證明這一命題. 關(guān)鍵字：最小正約數(shù)；Fermat數(shù)列；合數(shù)；調(diào)和級(jí)數(shù)；數(shù)學(xué)歸納法 1 引言 一個(gè)大于1的整數(shù)，除了1和它本身以外不能被其他正整數(shù)整除，就稱為素?cái)?shù).通常用字母p、q表示，例如1,2,3,5,7,11,13,17,都是素?cái)?shù).設(shè)x1,我們以x表示不超過(guò)x的素?cái)?shù)個(gè)數(shù).不難算出 x0x2 53

5、 10 50 415 歐幾里德的名著幾何原本第九篇的命題20證明了: 素?cái)?shù)的數(shù)目比以往任何指定的數(shù)目都要多，即素?cái)?shù)有無(wú)窮多個(gè): limxx 這樣把全體素?cái)?shù)按大小排列就得出一個(gè)無(wú)窮數(shù)列 2=p1p2p3pn 后來(lái)發(fā)現(xiàn)在全體正整數(shù)中素?cái)?shù)僅占很少一部分.下面我們就來(lái)證明一下這個(gè)命題. 2 引理、定理及證明 引理1設(shè)整數(shù)a1，他的大于1的最小正約數(shù)d必為素?cái)?shù). 1 d,所以證明 若d不是素?cái)?shù),則由素?cái)?shù)定義知,必有整數(shù)d,使得1d da但這與d的專家設(shè)矛盾.故而引理得證. 由此推出: 若a不是素?cái)?shù),則必有da. 引理2設(shè)有一個(gè)無(wú)限正整數(shù)列 1uu1u2u3s3如果它的任,意兩項(xiàng)均互素,則一定有無(wú)限多個(gè)素

6、數(shù). 證明設(shè)ds是us的大于1的最小正整數(shù),由此得到一個(gè)無(wú)限數(shù)列 d1,d2,ds,. 由假設(shè)知,它們也是兩兩互素的,所以是不同的整數(shù),而由引理1知ds均 為素?cái)?shù).這樣就證明了引理2. 引理31設(shè)整數(shù)a1,則a一定可以表為 12raq1q2q r (1) 其中qi均為素?cái)?shù), 且q1q2qr,以及整數(shù)i01ir 證明 當(dāng)a2時(shí),引理顯然成立.設(shè)n3,假設(shè)引理對(duì)所有的a2an均成立.當(dāng)n為素?cái)?shù)時(shí),則引理對(duì)于an顯然也成立;當(dāng)n不是素?cái)?shù)時(shí)設(shè)d是n的大于1的最小正約數(shù)ndn1.由引理1知d為素?cái)?shù).此外,這時(shí)必有2n1n,故由假設(shè)知n1可表為(1)的形式,所以n亦可表為這樣的形式,有歸納法知引理3成立.

7、 直接推論任一正整數(shù)a一定可表為 ak2l(2) 其中l(wèi)1,或是不同的素?cái)?shù)的乘機(jī), k是正整數(shù). 引理4設(shè)x2,我們有 3 111(3) a1axp1 其中求和號(hào)分展在所有不超過(guò)x的正整數(shù)上,連乘號(hào)分展在所有不超過(guò)x的素?cái)?shù)上. 證明 設(shè)2kx2k1.顯然有 11111111122kpppppppxpxpx1 1顯然出現(xiàn)在上式右邊的乘積中.注意到對(duì)于不同的a它們的表達(dá)式(1)一定是不同的,這就證明了引理4. 定理5 n!與n!1互素. n2 證明 首先證明n與n1互素 由于它們的最大公因子要整除它們的差,即n1n1,所以最大公因子只可為1,故而n與n1互素. 由此得 n2與n21互素, 因?yàn)樗鼈?/p>

8、的最大公因子只為1. 依次可得 n23n1與n23n11互素, 因?yàn)樗鼈兊淖畲蠊蜃又粸?. 即n!與n!1互素. 接下來(lái)我們開始證明定理 素?cái)?shù)的個(gè)數(shù)是無(wú)窮多的 證明 方法(一) 3 用反證法假設(shè)素?cái)?shù)只有有限個(gè) 即 2=p1p2ps 設(shè)np1p2ps1,d是它的大于1的最小正約數(shù),由引理一知d是素?cái)?shù).把全體素?cái)?shù)按大小順序排列,就得到一個(gè)無(wú)限數(shù)列,我們記為 2=p1,p2,ps,ps1,.定理得證 方法(二) 3 著名的Fermat數(shù)列 Fn221n0,1,2, n 就是滿足引理2中的條件的數(shù)列,顯然有 1F0F1FN 下面證明他們兩兩互素,設(shè)n0,k1,由 Fnk222n2k1 知FnFnk2

9、,設(shè)d=Fn,Fnk,因而必有d2, Fn均為奇數(shù),所以d1. 定理得證 方法(三) 3 設(shè)n2,對(duì)任意一個(gè)a1an,在它的表達(dá)式(2)中一定有 :1k1或l使一些不超過(guò)n的不同的素?cái)?shù)的乘積.這樣, k 可能取得值得個(gè)數(shù),而l所可能取的值的個(gè)數(shù)不超過(guò)以下的組合數(shù)之和 nnnn12. n12 所以必有 nn 1即 nlog2nn2 定理得證 2 n不超過(guò)n的素?cái)?shù)有n個(gè)，所有的k個(gè)不超過(guò)n的不同的素?cái)?shù)的乘積個(gè)數(shù)為k 由此即得所說(shuō)的結(jié)論. 方法(四) 3 如果只有有限個(gè)素?cái)?shù),那么式(3)的右邊當(dāng)x時(shí)為一有限數(shù).但是左邊的調(diào)和級(jí)數(shù)當(dāng)x時(shí)是發(fā)散的.這一矛盾就證明了定理. 方法(五) 由定理五,得n!與1

10、,2,3,n1,n互素,那么n!1有兩種可能(1) n!1為素?cái)?shù);(2) n!1為合數(shù). (1)設(shè)an!1為素?cái)?shù),集合Ax0xnxN有b個(gè)素?cái)?shù) 則集合Bx0xn!1xN內(nèi)至少有b+1個(gè)素?cái)?shù). (2)設(shè)an!1為合數(shù),則在集合B中至少有2個(gè)元素可以被a整除 A Ba可證C=minxx且hhN為素?cái)?shù).且(1)設(shè)集合A內(nèi)有b個(gè)素?cái)?shù),則集Ax 合B內(nèi)至少有b+1個(gè)素?cái)?shù).綜合(1)、（2）可得:設(shè)集合Ax0xnxN有b個(gè)素?cái)?shù). 則集合B內(nèi)至少有b+1個(gè)素?cái)?shù). 1xN內(nèi)至少由b+2個(gè)素?cái)?shù). 重復(fù)上述步驟可得集合C=x0xn!1！ 繼續(xù)沿用上述步驟,用數(shù)學(xué)歸納法可證:設(shè)集合Ax0xnxN有b個(gè)素?cái)?shù).則集合

11、Dx0x11，xNn重至少由b+d個(gè)素?cái)?shù). n!1！ 由此:當(dāng)d時(shí), e=素?cái)?shù)的個(gè)數(shù)b+d=+. 故可得素?cái)?shù)的個(gè)數(shù)是無(wú)窮多的. (指導(dǎo)老師:王明軍) _： 1張文鵬.初等數(shù)論M.西安:陜西師范大學(xué)出版社, 20xx-6 2歐幾里德.幾何原本M.北京: _出版社, 20xx-10 3潘承洞、潘承彪.素?cái)?shù)定理的初等證明M.上海:上海科技出版社, 1988-02 構(gòu)造法： 1.歐幾里得證法： 證：假設(shè)素?cái)?shù)只有有限個(gè)，設(shè)為q1,q2,.qn，考慮p=q1q2.qn+1。顯然，p不能被q1,q2,.qn整除。故存在兩種情況：p為素?cái)?shù)，或p有除q1,q2,.qn以外的其它素因子。無(wú)論何種情況，都說(shuō)明素?cái)?shù)不

12、止有限個(gè)。假設(shè)錯(cuò)誤，所以素?cái)?shù)有無(wú)窮多個(gè)5.| 2. 設(shè)p1,.,pn是n個(gè)兩兩不同的素?cái)?shù)。再設(shè)Ar是其中任意取定的r個(gè)素?cái)?shù)的乘積。證明：任一pj(1jn)都不能整除 p1.pn/Ar+Ar; 由此推出素?cái)?shù)有無(wú)窮多個(gè)。 證：因?yàn)閜j若不是Ar的因子，必然是p1.pn/Ar的因子；或者，pj若是Ar的因子，必然不是p1.pn/Ar的因子。因此，p1.pn/Ar+Ar或者是素?cái)?shù)，或者除p1,.,pn之外有其它素因子。無(wú)論何種情況，都說(shuō)明素?cái)?shù)不止有限個(gè)。假設(shè)錯(cuò)誤，所以素?cái)?shù)有無(wú)窮多個(gè)。 3.級(jí)數(shù)法： 假若素?cái)?shù)只有有限個(gè)p1,.,ps.證明：對(duì)任意正整數(shù)N必有 11111(1).(1)nppn11s。由此

13、推出素?cái)?shù)有無(wú)窮多個(gè)。 N 證： psp111111)(1).(1)p1psp11ps1 n1nN 11)1-1p1ps (1 111112.).(1.)p1p1psp1ps 1(因?yàn)槿我庹麛?shù)都可以表示成素?cái)?shù)或素?cái)?shù)的乘積） n1n 故上式成立。 因?yàn)榧?jí)數(shù)1n1n遞增，趨于正無(wú)窮大，由上式 n(1p) n11N111.(111)ps 可知：素?cái)?shù)有無(wú)窮多個(gè)。（否則，上式右側(cè)為常值） 4.Fermat數(shù)法： 設(shè)n0,Fn=22+1.再設(shè)mn.證明：若d1,且d|Fn,則d不整除n Fm.由此推出素?cái)?shù)有無(wú)窮多個(gè)。 證：設(shè)2m/2n=r,2n=p則 當(dāng)mn時(shí)，必有Fn|22-1=(22+1)(pr-1-pr-2+.-1) mn =(2+1)(1)k1prk=(22+1