有無限多個質數

一個大於1的正整數,如果它的正因數只有 2 個,就是 1 和正整數自己,則這個正整數就是質數(prime number).
古希臘數學家幾何之父 歐幾里德(Euclid)約在西元前300年左右就運用了反證法證明「質數有無限多個」,這就是數論中的歐幾里德定理,這定理就是幾何原本(Element)的第9卷第20命題。
我們
證明一個數學命題,通常會考慮運用直接證法,根據命題的已知條件與公理或定理做合乎邏輯的演繹推論。如果使用直接證法不容易推論,我們就考慮採用「反證法」。
「反證法」是先假設命題結論不成立,經由這個假設出發,依據命題條件推理,導出與假設矛盾的衝突結果,如此就可以推論原來的假設是錯誤的,所以原命題的結論是正確的。

歐幾里德
使用反證法證明「有無限多個質數」,其想法大致如下,
(1).先假設所有質數只有 n 個,也就是說質數的個數是有限的,例如,所有質數是P1 P2 P3...Pn
(2).因為存在一個整數 P=(P1 × P2 × P3 ×.....× Pn)+1其中Pi 可以整除P1 × P2 × P3 ×.....× Pn, i=1~n,可是Pi不能整除 1,所以Pi不能整除(P1 × P2 × P3 ×.....× Pn)+1,也就是說所有質數都不能整除P,可是P可以被1與P整除。推論至此,我們發現矛盾之處,因為P的正因數只有1與P,「P是質數,但是所有質數都不能整除P」,這個結果顯然是不合理的。這個矛盾肇因於錯誤的假設「質數的個數是有限n個」,所以「有無限多個質數」才是正確的命題。

 

一些數學家使用直接證法證明「質數有無限多個」,西元2005年由任教於美國北卡羅來納大學(University Of North Carolina) 數學系的 Filip Saidak 教授所提出,其想法大致如下,
(1).兩個大於1的連續正整數N與N+1,由
輾轉相除法原理可知N與N+1的最大公因數等於1與N的最大公因數,而1與N的最大公因數是1,所以N與N+1的最大公因數是1,也就是說N與N+1「沒有共同的質因數」,通常我們稱N與N+1互質。

(2).如果整數 N2是N與(N+1)的乘積,即N2=N(N+1),由論述(1)可知N2至少有2個不同的質因數。
(3).如果整數 N3是N2與(N2+1)的乘積,即N3=N2(N2+1),由論述(1)(2)可知N2與(N2+1)「沒有共同的質因數」,又已知N2至少有2個不同的質因數,所以N3至少有3個不同的質因數。
(4).由上述推論可知x>1,Nx=Nx-1(Nx-1+1),則Nx至少有x個不同的質因數。如果x一直繼續無止境的增大,則Nx的質因數個數也無止境的增加,所以「質數有無限多個
」。

 

參考資料

1. http://primes.utm.edu/notes/proofs/infinite/

 


Copyright ©昌爸工作坊 all rights reserved.