質數有無限多個-Sep08

前幾天 已知的最大質數又有新發現了(新聞連結)
據說質數的找尋在密碼學中扮演一席之地
只是要怎麼運用這些質數我就不知道了
索性google了一下 忽然喚起了高中數學的記憶
質數其中有一個性質就是 "質數有無限多個"
那所謂的質數(prime)必須符合下列條件:
1.大於1的自然數
2.因數只有1和自己
至於證明"質數有無限多個"的方法 看完之後覺得很有趣 就記錄下來

利用的是歸謬證法(假設一個跟命題相反的假設, 然後證明假設是錯的)

命題:質數有無限多個
假設:質數是有限多個(n個)

設最大質數為 pn
所有質數集合:{p1, p2, p3...pn}
設 M = p1*p2*p3*...*pn + 1

因為 pn為最大質數 => M為合數
但是 M不能被所有質數整除(皆餘1)
所以 M為質數

又因為 M > pn => 與假設矛盾
所以質數有無限多個

PS:
複習完這個證明,
突然可以體會古代數學家的那種樂趣
呵。呵。呵。