開主選單
數學
基本

延伸

其他

圓周率 π = 3.141592653…
自然對數嘅底 e = 2.718281828…
虛數單位 i = 
無窮大量 

質數粵拼zat1 sou3),又叫素數sou3 sou3),係個大過1自然數,除咗自己同1之外,無其他數可以將佢整除。質數有無限個,公元前300年左右,歐幾理德(Euclid)證明過呢點。質數有時亦為都叫素數,而英文就叫質數做prime number或者prime

如果同係大過1嘅自然數,又只唔係質數嘅數,就叫合成數。合成數都係由大過1嘅自然數相乘而來。

頭三十個質數分別係2357111317192329313741434753596167717379838997101103107109同埋113

定義

假設 係一個整數。如果 只有 同埋 係佢嘅因數(Factor),咁 就係一個質數。唔係嘅話, 就係一個合成數(Composite Number)。 同埋 冇定義。

搵法

 
愛氏篩搵120以內質數嘅演算法

搵質數最簡單係用愛氏篩(Sieve of Eratosthenes)。

歐幾理得推論

歐幾理得推論(質數版)

如果 係一個質數同埋 ,咁就一係 或者 

證明:

假設 唔可以被 整除,即係 

因為 ,利用相對質數性質,得出 

由上可得推理:

如果 係一個質數同埋 ,咁樣  係一個自然數符合 

呢個推理指嘅係,如果質數 除得盡一個合成數,呢個合成數由 個數字乘出嚟,佢嘅因數就叫做 ,咁樣 一定除得盡其中一個因數。

證明:

利用歐幾理得推論, 或者 

再利用多一次,得出 或者 

如此類推, 或者 或者 或者 ,結果就係一定除得盡其中一個。

歐幾理得證明

存在無限質數。

證明: 假設得 咁多個質數,叫 ,而家考慮一個整數 

假設 係一個質數。

因為佢係上面講嘅樣,所以唔止得 咁多個質數,令到同第一句有矛盾,所以 唔可以係質數。

根據質數分解 一定可以被一啲(即係上面n咁多個其中)質數除得盡,但係根據餘數定理 係唔可能俾上面n個質素除得盡,

即係   一定有   唔可以被整除,

所以 係一個質數。因為咁令到同第一句有矛盾。

以上兩個情況都出現咗矛盾,即係話假設出錯,質數一定係有無限咁多個。

睇埋