質數

出自維基百科,自由嘅百科全書
跳去: 定向搵嘢
數學
基本

自然數
整數
二進分數
有限小數
循環小數
有理數
高斯整數
代數數
實數
複數

負數
分數
單位分數
無限小數
規矩數
無理數
超越數
二次無理數
虛數
艾森斯坦整數

延伸

雙複數
四元數
共四元數
八元數
超數
上超實數
超現實數

超複數
十六元數
複四元數
Tessarine
大實數
超實數

其他

對偶數
雙曲複數
序數
質數
同餘
可計算數
艾禮富數

公稱值
超限數
基數
P進數
規矩數
整數序列
數學常數

圓周率 π = 3.141592653…<NoInclude>

[]

自然對數嘅底 e = 2.718281828…<NoInclude>

[]

虛數單位 i = <NoInclude>

[]

無窮大量 <NoInclude>

[]

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

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

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

定義[編輯]

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

搵法[編輯]

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

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

歐幾理得推論[編輯]

歐幾理得推論(質數版)

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

證明:

假設唔可以被整除,即係

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

由上可得推理:

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

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

證明:

利用歐幾理得推論,或者

再利用多一次,得出或者

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

歐幾理得證明[編輯]

存在無限質數。

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

假設係一個質數。

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

根據質數分解一定可以被一啲(即係上面n咁多個其中)質數除得盡,但係根據餘數定理係唔可能俾上面n個質素除得盡,所以係一個質數。因為咁令到同第一句有矛盾。

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

睇埋[編輯]