質數是無限的，如何證明?!

rad42183

我們老師下課前問了這題
還說了最早是歐幾里得證出來的

當然   數是無限的，質數也是無限的
這大家都知道
可是我想不出來如何證明出來= ="

煩請板上高明解惑...
謝謝!

傲月光希

用反證法
假設質數有限個，則存在最大的質數A，a1,a2,...,A都是質數且a1<a2<...<A
令M=a1*a2*...*A+1
則M不能被任何小於等於A的質數所整除，因此M一定會被某個大於A的質數整除或者M也是個質數
若M要被大於A的質數整除，則與原設矛盾(A不是最大質數)
若M是個質數，M>A，則與原設矛盾(A不是最大質數)

所以質數是無限個

[ 本文最後由 傲月光希 於 06-7-30 02:02 AM 編輯 ]

M.N.M.

原文由 傲月光希 於 06-7-30 01:59 AM 發表
用反證法
假設質數有限個，則存在最大的質數A，a1,a2,...,A都是質數且a1<a2<...<A
令M=a1*a2*...*A+1
則M不能被任何小於等於A的質數所整除，因此M一堮..

補充:此證法是"歐幾里德"的證法

首先要先知道"由2開始將一連串的質數相乘後加1，就會創造新的質數!"才能了解
這證法

[ 本文最後由 M.N.M. 於 06-7-30 01:18 PM 編輯 ]

ksitrcuser

原文由 M.N.M. 於 06-7-30 01:14 PM 發表

補充:此證法是"歐幾里德"的證法

首先要先知道"由2開始將一連串的質數相乘後加1，就會創造新的質數!"才能了解
這證法

可惜這個方法求出來的不一定是質數(2*2*2+1=9  2*7+1=15)

有規定每個質數的限用次數嗎

不然用這個方法求質數很快呢

神光

原文由 ksitrcuser 於 06-7-30 03:17 PM 發表


可惜這個方法求出來的不一定是質數(2*2*2+1=9  2*7+1=15)

有規定每個質數的限用次數嗎

不然用這個方法求質數很快呢

這方法是將由2開始的一連串質數相乘吧?
2*2*2+1,2*7+1好像不行

M.N.M.

意思是這樣的，中間不可間斷也不可重覆

2*3+1=7是質數

2*3*5+1=31是質數

2*3*5*7+1=211是質數

ksitrcuser

原文由 M.N.M. 於 06-7-30 03:41 PM 發表
意思是這樣的，中間不可間斷也不可重覆

2*3+1=7是質數

2*3*5+1=31是質數

2*3*5*7+1=211是質數

2*5+1=11

2*2*3+1=13

2*2*2*2+1=17

2*3*3+1=19
     .
     .
     .
難道這些質數不符合此公式?

還是說此公式只是用來證明質數有無限個?

[ 本文最後由 ksitrcuser 於 06-7-30 05:28 PM 編輯 ]

M.N.M.

原文由 ksitrcuser 於 06-7-30 05:26 PM 發表


2*5+1=11

2*2*3+1=13

2*2*2*2+1=17

2*3*3+1=19
     .
     .
     .
難道這些質數不符合此公式?

還是說此公式只是用來證明質數有無限個?

在下對此公式的確是這樣的= =a

M.N.M.

才發現這證法有蠻多的問題

2*3*5*7*11*13+1=59*509

所以不能說明這公式一定是質數(囧

傲月光希

原文由 M.N.M. 於 06-7-31 09:32 AM 發表
才發現這證法有蠻多的問題

2*3*5*7*11*13+1=59*509

所以不能說明這公式一定是質數(囧

還好我有考慮到M可能是合成數的情形~囧