跳至內容

歐幾里得定理

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

歐幾里得定理數論中的基本定理,定理指出素數的個數是無限的。該定理有許多著名的證明。

歐幾里得的證明

[編輯]

歐幾里得在他的著作《幾何原本》(第九卷的定理20)[1]提出了證明,大意如下[2]

對任何有限素數的集合。在這裡將會證明最少存在一個集合中沒有的額外素數。令。那麼是素數或者不是,二者必居其一:

  • 如果是素數,那麼至少有一個素數不在有限素數集中。
  • 如果不是素數,那麼存在一個素數因子整除,如果在我們的有限素數集中,必然整除(既然是素數有限集中所有素數的積);但是,已知整除(),如果同時整除必然整除之差[3] —— 。但是沒有素數能整除,即有整除就不存在整除。因此不在有限集中。

這證明了:對於任何一個有限素數集,總存在一個素數不在其中。所以素數一定是無限的。

很多時候有人會錯誤地指出歐幾里得是用了反證法,他們假設證明起初考慮的是所有自然數的集合,或是集合內含有個最小的素數,而不是任何任意的素數集合[4]。歐幾里得證明用的不是反證法,而是證明了一個有限集合中沒有任何擁有特殊性質的元素。當中並沒有反論的部分,但集合中的任何元素都不可以整除1。

文獻中存在數個版本的歐幾里得證明,包括以下的:

正整數的階乘可被的所有整數整除,這是由於它是這些數全部的乘積。因此並不能被(包括)的任何自然數所整除(所得的餘數皆為)。因此有兩個可能性:是素數,或者能被大於所整除。在任一個案中,對所有正整數而言都存在最少 一個比大的素數。所以結論就是共有無限個素數[5]

歐拉的證明

[編輯]

另一個由瑞士數學家萊昂哈德·歐拉提出的證明,則使用了算術基本定理:每一個自然數都有一組獨一無二的素因子排列。設為所有素數的集合,歐拉寫下了:

第一條等式是由乘積中每一項的等比數列公式所得。而第二個等式則是用於黎曼ζ函數歐拉乘積。為了證實此點,可把乘積分配進和裡面:

在這個結果中,每一個素數積都出現了正好一次,因此由算術基本定理可得這個和等於所有自然數的和。

右邊的和是發散的調和級數。因此左邊的和也是發散的。由於乘積內每一個項都是有限的,所以其項數必須為無限;因此得出共有無限個素數。

埃爾德什的證明

[編輯]

埃爾德什·帕爾的第三種證明也是靠算術基本定理的。首先注意每一個自然數都能被寫成獨一無二的

其中平方數,或任何平方數的倍數(設為能整除的最大平方數,並使)。此時假設素數的數量為有限,且其數量為。由於每個素數只有一個非平方數的因子,所以根據算術基本定理,得出共有非平方數個。(見組合#在集合中取出k項元素

現在把一個正整數固定,並考慮1與之間的自然數。 這些數每一個都能被寫成,其中為非平方數,為平方數,例如:

集合中共有個不同的數。每一個都是由非方數和比小的平方數組成。這樣的平方數共有(見高斯符號的取底符號)。然後把這些小於的平方數乘積與其餘所有的非平方數相乘。這樣得出的數一共有個,各不相同,因此它們包括了所有我們集合裡的數,甚至更多。因此,

由於此不等式對足夠大的並不成立,因此必須存在無限個素數。

弗斯滕伯格的證明

[編輯]

哈里·弗斯滕伯格英語Hillel Furstenberg於1950年代提出了一個使用點集拓撲學的證明。(見弗斯滕伯格對素數無限性的證明英語Furstenberg's proof of the infinitude of primes

一些近期的證明

[編輯]

皮納西科

[編輯]

胡安·帕布洛·皮納西科(Juan Pablo Pinasco)寫下了以下的證明[6]

為最小的個素數。然後根據容斥原理可得,少於或等如又同時能被那些素數中其中一個整除的正整數的個數為

把全式除以,並且讓,得

上式可被改寫為

若除了以外不存在其他素數的話,則式(1)與 相等,而式(2)則等於,但很明顯地式(3)並不等於。因此除了以外必須要存在其他素數。

[編輯]

俊浩·彼得·黃(Junho Peter Whang)於2010年發表了使用反證法的證明[7]。設為任何正整數,為素數。根據勒讓德定理,則可得:

其中

但若只存在有限個素數,則

(上式分子呈單指數增長,但斯特靈公式指出分母的增長速度比分子快),這樣就違反了每一個的分子要比分母大的這一點。

塞達克

[編輯]

菲利浦·塞達克(Filip Saidak)給出了以下的證明,當中沒有用到歸謬法 (而大部分歐幾里得定理的證明都用了,包括歐幾里得自己的證明),而同時不需要用到歐幾里得引理,也就是若素數整除則也必能整除。證明如下:

由於每個自然數()最少擁有一個素因子,所以兩個相鄰數字必定沒有共同因子,而乘積則比數字本身擁有更多因子。因此普洛尼克數的鏈:
1×2 = 2 {2},    2×3 = 6 {2, 3},    6×7 = 42 {2,3, 7},    42×43 = 1806 {2,3,7, 43},    1806×1807 = 3263443 {2,3,7,43, 13,139}, · · ·
提供了一組素數集合無限增長的數列。

使用π的無理性的證明

[編輯]

以歐拉乘積來表示π的萊布尼茨公式可得[8]

乘積的分子為奇數的素數,而每一個分母則是最接近分子的4的倍數。

若存在的素數是有限的話,上式所展示的就是π是一個有理數,而分母是所有與素數多1或少1的4的倍數的乘積,而這點違反了π實際上是無理數的這一點。

使用信息論的證明

[編輯]

亞歷山大·沈(音譯,Alexander Shen)與其他人發表了利用不能壓縮性英語Incompressiblity method的證明[9]

設只存在素數()。由算術基本定理可得,任何正整數都能被寫成:

其中非負自然數與素數的有限集合就足夠重構任何數字。由於所有都遵守,因此可得所有\(其中代表底數為2的對數)。

由此可得的編碼大小(使用大O符號):

位元

(其中prime list size為素數集合的大小)這編碼比直接用二進制代表要有效得多,二進制的話需要位元。無損數據壓縮的一個已被確立的結果指出,一般不可能把位元的信息壓縮到少於位元。由於,所以當足夠大時,以上的這個表示不成立。

因此,素數的數量必不能為有限。

參閱

[編輯]

注釋和參考資料

[編輯]
  1. ^ James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63.
  2. ^ 歐幾里德主張的準確表述為:「素數比任何可以提出的量都要多」。在這個證明中,假定了最少存在三個素數,歐幾里得則由此推論出必存在第四個素數。
  3. ^ 一般來說,對任何整數而言,若成立的話,則必成立。見整除性
  4. ^ Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, volume 31, number 4, fall 2009, pages 44–52.
  5. ^ Bostock, Linda; Chandler, Suzanne; Rourke, C. Further Pure Mathematics. Nelson Thornes. 2014-11-01: 168. ISBN 9780859501033 (英語). 
  6. ^ Juan Pablo Pinasco, "New Proofs of Euclid's and Euler's theorems", American Mathematical Monthly, volume 116, number 2, February, 2009, pages 172–173.
  7. ^ Junho Peter Whang, "Another Proof of the Infinitude of the Prime Numbers", American Mathematical Monthly, volume 117, number 2, February 2010, page 181.
  8. ^ Debnath, Lokenath, The Legacy of Leonhard Euler: A Tricentennial Tribute, World Scientific: 214, 2010 [2017-07-13], ISBN 9781848165267, (原始內容存檔於2016-07-30) .
  9. ^ Shen, Alexander, Kolmogorov complexity and algorithmic randomness (PDF), AMS: 245, 2016 [2017-07-13], (原始內容存檔 (PDF)於2017-08-21) 

外部連結

[編輯]