質數

出自維基百科,自由嘅百科全書
數學
基本

延伸

其他

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

質數粵拼zat1 sou3),又叫素數sou3 sou3),係個大過 1自然數,除咗自己同 1 之外,無其他數可以將佢整除英文入面叫質數做prime number或者prime

大過1又唔係質數嘅自然數就叫合成數,合成數都係由大過1嘅自然數相乘而來。例如 5 就係質數,因為要將 5 寫做乘積嘅話,就一定係 或者係 ,點都要用返 5 自己。4 就係一個合成數,因為可以將 4 寫做,用兩個細啲嘅數相乘而得到 4。

喺數論入面,質數好重要,因為算術基本定理指出,大過 1 嘅自然數,一係佢已經係質數,一係佢可以寫做一柞質數乘埋,而且呢個寫法唔計次序嘅話係唯一嘅。

質數有無限個,公元前300年左右,歐幾理德(Euclid)證明過呢點。頭三十個質數係2357111317192329313741434753596167717379838997101103107109同埋113。(OEIS數列A000040

定義[編輯]

假設 係一個整數。如果 只有 同埋 係佢嘅因數(factor),咁 就係一個質數。唔係嘅話, 就係一個合成數(composite number)。 同埋 就質數、合成數兩者都唔係。

搵法[編輯]

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

搵質數最簡單係用愛氏篩(Sieve of Eratosthenes),即係先將第一個質數(即係2)嘅倍數篩走,跟住將下一個質數(即係3)嘅倍數篩走,如此類推。

歐幾理得推論[編輯]

歐幾理得推論(質數版)

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

證明:

假設唔可以被整除,即係

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

由上可得推理:

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

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

證明:

利用歐幾理得推論,或者

再利用多一次,得出或者

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

歐幾理得證明[編輯]

存在無限質數。

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

假設係一個質數。

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

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

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

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

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

睇埋[編輯]