如何證明形如4n+3的素數有無限多個
篇一：證明形如4n+3的素數有無限多個
四、證明題（每小題10分，3題共30分）
1.證明：形如4n+3（n為非負整數）的素數有無限多個.
證明：用反證法
若形如4n3的素數為有限個，設為p1,p2,pk.(整個證明的思想是用反正法，先設形如4n+3的素
數只有有限個，設為p1,p2,pk，再找到4n+3形式
的數p,并且這個p是不等于p1,p2,pk的，這樣就與
我們假設的有限個就矛盾了)
令q4p1p2pk14(p1p2pk1)3，（現在構造一個數q，通過變形我們知道q也是4n+3
形式的數，顯然qpi,i1,2,.....k（若相等則有
(4p1p2pi1pi1pk1)pi1，這不可能），若q已經為
素數，就找到了不等于p1,p2,pk的素數q，定理已
經得證，若q不是素數，我們考慮它的素因數，在
下面的步驟）
顯然pi都除不盡q.（反證法，若能除盡，即piq，而由上面可知14p1p2pkq，則有pi1，矛盾） 若q為素數，而qpi，i1,2,.....k，定理已經得證.（這個結論上面的注已經說明）
現在考察q不是素數，那么它必有素因數 （一個數能分解為若干素數的乘積） (4l1)(4m1)4(4lmlm)14u1，（此式子說明4n+1形式的乘積還是4n+1的形式） 而q一定不能全是4n1形式素因數，
一定還有4n3形式的素因數p， （因為q也是4n+3的形式，若全是4n+1的形式，
它們的乘積得不到4n+3的形式，故一定還有
4n3
形式素因數p. 由假設知q是奇數，它的因
數肯定都是奇數，所以它的因數要么是4n+1的形
式，要么是4n+3的形式，不可能是4n+2與4n+4
的形式（因為這兩個還是偶數））
且不是p1,p2,pk中的一個，與假設矛盾. （前面已經證明pi都除不盡q，而p是q的因數，
因此p能整除q，故p不是p1,p2,pk中的一個）
故形如4n3的素數有無限多.（一開始我們假設的是有限個，k個，而現在我們
找到了不等于p1,p2,pk的其它的4n+3形式的素
數p，順環往復，這說明有限個的假設不正確，
故形如4n+3的素數有無限多個）
注：主要步驟就是黑字的'部分，后面的彩色的字是我做的注解，做題目的時候可以不寫。
篇二：論文：關于素數有無窮多個的證明
摘要：有關于素數的個數是無窮多個的定理有許多的證明方法，最早的證明要見于歐幾里德的名著《幾何原本》第九篇的命題20中：素數的數目比以往任何指定的數目都要多，即素數有無窮多個.本文在總結前人證明的基礎上用數學歸納法再次證明這一命題. 關鍵字：最小正約數；Fermat數列；合數；調和級數；數學歸納法 1 引言
一個大于1的整數，除了1和它本身以外不能被其他正整數整除，就稱為素數.通常用字母p、q表示，例如1,2,3,5,7,11,13,17,都是素數.設x1,我們以x表示不超過x的素數個數.不難算出
x0x2 53 10 50 415
歐幾里德的名著《幾何原本》第九篇的命題20證明了: 素數的數目比以往任何指定的數目都要多，即素數有無窮多個:
limxx
這樣把全體素數按大小排列就得出一個無窮數列
2=p1p2p3pn
后來發現在全體正整數中素數僅占很少一部分.下面我們就來證明一下這個命題.
2 引理、定理及證明
引理1設整數a1，他的大于1的最小正約數d必為素數. 1
d,所以證明 若d不是素數,則由素數定義知,必有整數d,使得1d<d , d
da但這與d的專家設矛盾.故而引理得證.
由此推出: 若a不是素數,則必有da.
引理2設有一個無限正整數列 1uu1u2u3s3如果它的任,意兩項均互素,則一定有無限多個素數.
證明設ds是us的大于1的最小正整數,由此得到一個無限數列
d1,d2,ds,.
由假設知,它們也是兩兩互素的,所以是不同的整數,而由引理1知ds均
為素數.這樣就證明了引理2.
引理31設整數a1,則a一定可以表為
12raq1q2q
r (1)
其中qi均為素數, 且q1q2qr,以及整數i01ir
證明 當a2時,引理顯然成立.設n3,假設引理對所有的a2an均成立.當n為素數時,則引理對于an顯然也成立;當n不是素數時設d是n的大于1的最小正約數ndn1.由引理1知d為素數.此外,這時必有2n1n,故由假設知n1可表為(1)的形式,所以n亦可表為這樣的形式,有歸納法知引理3成立. 直接推論任一正整數a一定可表為
ak2l(2)
其中l1,或是不同的素數的乘機, k是正整數.
引理4設x2,我們有 3
111(3) a1axp1
其中求和號分展在所有不超過x的正整數上,連乘號分展在所有不超過x的素數上.
證明 設2kx2k1.顯然有
11111111122kpppppppxpxpx1
1顯然出現在上式右邊的乘積中.注意到對于不同的a它們的表達式(1)一定是不同的,這就證明了引理4.
定理5 n!與n!1互素. n2
證明 首先證明n與n1互素
由于它們的最大公因子要整除它們的差,即n1n1,所以最大公因子只可為1,故而n與n1互素.
由此得 n2與n21互素, 因為它們的最大公因子只為1.
依次可得 n23n1與n23n11互素, 因為它們的最大公因子只為1.
即n!與n!1互素.
接下來我們開始證明定理 素數的個數是無窮多的
證明 方法(一) 3
用反證法假設素數只有有限個 即
2=p1p2ps
設np1p2ps1,d是它的大于1的最小正約數,由引理一知d是素數.把全體素數按大小順序排列,就得到一個無限數列,我們記為
2=p1,p2,ps,ps1,.定理得證
方法(二) 3
著名的Fermat數列
Fn221n0,1,2,, n
就是滿足引理2中的條件的數列,顯然有
1F0F1FN
下面證明他們兩兩互素,設n0,k1,由
Fnk222n2k1 知FnFnk2,設d=Fn,Fnk,因而必有d2, Fn均為奇數,所以d1. 定理得證 方法(三) 3
設n2,對任意一個a1an,在它的表達式(2)中一定有
:1k1或l使一些不超過n的不同的素數的乘積.這樣, k
可能取得值得個數,而l所可能取的值的個數不超過以下的組合數之和
nnnn12. n12
所以必有
nn
1即 nlog2nn2 定理得證 2
n（）不超過n的素數有n個，所有的k個不超過n的不同的素數的乘積個數為k
由此即得所說的結論.
方法(四) 3
如果只有有限個素數,那么式(3)的右邊當x時為一有限數.但是左邊的調和級數當x時是發散的.這一矛盾就證明了定理.
方法(五)
由定理五,得n!與1,2,3,n1,n互素,那么n!1有兩種可能(1) n!1為素數;(2) n!1為合數.
(1)設an!1為素數,集合Ax0xnxN有b個素數 則集合Bx0xn!1xN內至少有b+1個素數.
(2)設an!1為合數,則在集合B中至少有2個元素可以被a整除 A
Ba可證C=minxx且hhN為素數.且(1)設集合A內有b個素數,則集Ax
合B內至少有b+1個素數.綜合(1)、（2）可得:設集合Ax0xnxN有b個素數. 則集合B內至少有b+1個素數.
1xN內至少由b+2個素數. 重復上述步驟可得集合C=x0xn!1！
繼續沿用上述步驟,用數學歸納法可證:設集合Ax0xnxN有b個素數.則集合
Dx0x11，xNn重至少由b+d個素數. n!1！！
由此:當d時, e=素數的個數b+d=+.
故可得素數的個數是無窮多的.
(指導老師:王明軍)
參考文獻：
1張文鵬.初等數論M.西安:陜西師范大學出版社, 2007-6
2歐幾里德.幾何原本M.北京:人民日報出版社, 2005-10
3潘承洞、潘承彪.素數定理的初等證明M.上海:上海科技出版社, 1988-02
篇三：素數有無窮多個的幾個證明
構造法：
1.歐幾里得證法：
證：假設素數只有有限個，設為q1,q2,...qn，考慮p=q1q2...qn+1。顯然，p不能被q1,q2,...qn整除。故存在兩種情況：p為素數，或p有除q1,q2,...qn以外的其它素因子。無論何種情況，都說明素數不止有限個。假設錯誤，所以素數有無窮多個5.|
2.
設p1,...,pn是n個兩兩不同的素數。再設Ar是其中任意取定的r個素數的乘積。證明：任一pj(1≤j≤n)都不能整除 p1...pn/Ar+Ar;
由此推出素數有無窮多個。
證：因為pj若不是Ar的因子，必然是p1...pn/Ar的因子；或者，pj若是Ar的因子，必然不是p1...pn/Ar的因子。因此，p1...pn/Ar+Ar或者是素數，或者除p1,...,pn之外有其它素因子。無論何種情況，都說明素數不止有限個。假設錯誤，所以素數有無窮多個。
3.級數法：
假若素數只有有限個p1,...,ps.證明：對任意正整數N必有 11111(1)...(1)nppn11s。由此推出素數有無窮多個。 N
證：
psp111111)(1)...(1)p1psp11ps1 n1nN
11)1-1p1ps
(1
111112...)...(1...)p1p1psp1ps 1(因為任意正整數都可以表示成素數或素數的乘積） n1n
故上式成立。
因為級數1n1n遞增，趨于正無窮大，由上式
n(1p)
n11N111...(111)ps
可知：素數有無窮多個。（否則，上式右側為常值）
4.Fermat數法：
設n≥0,Fn=22+1.再設m≠n.證明：若d>1,且d|Fn,則d不整除n
Fm.由此推出素數有無窮多個。
證：設2m/2n=r,2n=p則
當m>n時，必有Fn|22-1=(22+1)(pr-1-pr-2+...-1) mn
=(2+1)(1)k1prk=(22+1)q=Fm-2. 2n
k1
由條件可得：d|Fm-2,又d>1,且d|Fn,故d≥3.則d不整除Fm. 當m<n時，假設d|Fm,推出d不整除Fn.
由以上命題：假設di均為素數且ni遞增，則
d1|Fn1→d1不整除Fn2;
d2|Fn2→d1,d2不整除Fn3;
……
由以上論證過程，可以證明素數有無窮多個。
5.
設A1=2，An+1=An2-An+1(n≥1).再設n≠m.證明：若d|An,d>1,d不整除Am.由此推出素數有無窮多個。
證：當m>n時必有An|Am-1.方法同上。
綜上所述：以上證明可以分為兩類：
第一類：1.2.3.同樣用到了反證法，構造法。首先假設素數有有限個，通過構造數列，論證矛盾。
第二類：4.5.用到了構造法，直接證明法。通過構造數列，證明素數有無窮多個。
【如何證明形如4n+3的素數有無限多個】相關文章：
什么是素數有哪些09-02
什么是素數有哪些？09-23
形如凄美愛情的詩句11-11
素數怎么判斷09-24
素數是什么10-12
形如槁木成語解析03-10
我有很多個母親初中作文07-22
《素數與合數》的教學反思06-30
素數指的是什么09-30