1.1質數(Prime Number)

1.1質數(Prime Number)

 　

定義： 一個正整數，除了1與自己本身之外，不能被任何正整數整除的數字

Q:質數的個數有幾個？

Ans：

　　我認為是無限多個，因為P₁  x P₂ x P₃ x P₄……+1都可能是個質數，所以乘越多的話就可能出現無限多個。

證明：(歐基里德證明法)

　　假設質數是有限個，且令它們為P₁、P₂、P₃…………P_n

(除了P₁、P₂、P₃…………P_n之外的正整數皆為非質數)，則P=P₁+P₂+P₃+……Pn+1為正整數，且P一定為非質數，非質數可被至少一個質數整除，即P至少被P₁、P₂、P₃……Pn其中一數整除

→ P/P₁ 餘1

   P/P₂ 餘1

   P/P₃ 餘1

   P/P_n 餘1

→P不被P1、P2、P3……Pn其中一數整除，故矛盾

所以得證　質數有無限多個　

	重點： 對任意正整數同餘，可以把整數分為n個不相交的子集合，如下 N0= {x≡0  mod N}            N1= {x≡1  mod N} N2= {x≡2  mod N}    ……    Nn-1= {x≡N-1  mod N}

Q:如何判定一個數是否為質數？

Ans：

　　n為正整數，n若不能被小於根號n之質數整除，n必為質數。

證明：

　　若n為複合數，則n可寫成下列式子  n=P1*P2= √n*√n

可知P1或P2必有一數會小於或等於√n

首先令P1≦√n

(1)若P1為質數，則得證 (即n可被小於或等於√n之質數整除)

(2)若P2為複合數，則P1可被小於P1之質數整除
→ 亦即n可被小於或等於√n之質數整除

由(1)(2)得知得證n可被小於或等於√n之質數整除

練習題：
(1)利用上述方法求小於100之質數

(2)利用上述方法求小於200之質數

(3)利用上述方法求小於300之質數

(4)利用上述方法求小於1000之質數

練習題：

找一個猜中質數機率較高的公式或演算法

Ans：

     n*(n+1)

補充：　有關質數議題－梅森數

梅森數，1903年,在美國紐約的一個學術報告會上,數學家科爾表演了一個小插曲:他走上講臺,拿起粉筆,一言不發,在黑板上做長長的計算。 算呀算呀,算出一個結果:

　　2⁶⁷-1=147573952589676412927。

然後又算呀算呀,又算出一個結果:

　　193707721×761838257287

　　=147573952589676412927。

兩次計算的結果完全相同,觀眾席上掌聲雷動。 臺上的人不作任何解釋,臺下的人不提任何問題,卻能完全互相了解,共享成功的喜悅。他們是打的什麼啞謎?究竟是怎麼一回事呢? 原來,科爾是在報告他自己關於質數研究的一個好結果。他的計算表明,2⁶⁷-1不是質數,因為它可以分解成兩個大於1的自然數的乘積。不是質數的自然數太多太多,大部份自然數都是合數。為什麼證明了2⁶⁷-1不是質數就要鼓掌呢? 這是因為2⁶⁷-1屬於一類著名的數,叫做"梅森數"。梅森是法國數學家,他研究過形如2p-1的數,其中p是質數,後來人們稱這類數為梅森數。梅森證明了,當p=2,3,5.7,13,17,19.31時,對應的8個梅森數都是質數。由此猜想,在梅森數中出現質數的機會可能比較多。人們要尋找更大的新質數,往往就到梅森數裡去淘金。在1903年科爾報告之前,當時的數學家們還指望2⁶⁷-1能被確定是一個大的質數。科爾通過板演,告訴他的同行們,2⁶⁷-1不是質數,是一個有21位的合數,不必再為它耗費時間做大量計算了。科爾還具體求出這個大合數的兩個質因數,其中一個是9位數,另一個是12位數。

如果一個梅森數是質數,就叫做梅森質數。通常打破大質數紀錄的都是梅森數。

1985年發現的大質數是第30個梅森質數.有65050位數字。這個紀錄在7年後被刷新,1992年發現了第31個梅森質數,有227832位數字。1994年發現了第32個梅森質數,有258716位數字。 1996年發現了第33個梅森質數,有378632位數字,它是21257787-1。梅森數除去對尋找大質數有特殊貢獻而外,在編碼中也有實際應用。