如何證明形如4n3的素數有無限多個

篇一：證明形如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.西安:陝西師範大學出版社, 20xx-6

2歐幾里德.幾何原本M.北京:人民日報出版社, 20xx-10

3潘承洞、潘承彪.素數定理的初等證明M.上海:上海科技出版社, 1988-02

篇三：素數有無窮多個的幾個證明

構造法：

1.歐幾里得證法：

證：假設素數只有有限個，設為q1,q2,，考慮p=+1。顯然，p不能被q1,q2,整除。故存在兩種情況：p為素數，或p有除q1,q2,以外的其它素因子。無論何種情況，都説明素數不止有限個。假設錯誤，所以素數有無窮多個5.|

2.

設p1,...,pn是n個兩兩不同的素數。再設Ar是其中任意取定的r個素數的乘積。證明：任一pj(1≤j≤n)都不能整除 ;

由此推出素數有無窮多個。

證：因為pj若不是Ar的因子，必然是的因子；或者，pj若是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

可知：素數有無窮多個。（否則，上式右側為常值）

at數法：

設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.用到了構造法，直接證明法。通過構造數列，證明素數有無窮多個。