關於素數有無窮多個的幾個證明

構造法：

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必有。由此推出素數有無窮多個。

證： (因為任意正整數都可以表示成素數或素數的乘積）

故上式成立。

因為級數遞增，趨於正無窮大，由上式可知：素數有無窮多個。（否則，上式右側為常值）

4.Fermat數法：

設n≥0,Fn=+1.再設m≠n.證明：若d>1,且d|Fn,則d不整除Fm.由此推出素數有無窮多個。

證：設2m/2n=r,2n=p則

當m>n時，必有Fn|-1=(+1)(pr-1-pr-2+...-1)

=(+1)=(+1)q=Fm-2.

由條件可得：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.用到了構造法，直接證明法。透過構造數列，證明素數有無窮多個。

假設存在一個最大的素數An.

之前的素數分別是A1,A2,A2,A3,.......An

那麼A1乘A2.....乘An+1 （即所有素數相乘再+1）=Am

由素數的定義可知Am仍然為素數，而且Am大於An.說明最出假設是錯誤矛盾的。反證了質數是無限的