質數

出自維基百科,自由嘅百科全書
Jump to navigation Jump to search
數學
基本

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

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

延伸

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

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

其他

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

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

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

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

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

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

定義[編輯]

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

搵法[編輯]

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

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

歐幾理得推論[編輯]

歐幾理得推論(質數版)

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

證明:

假設唔可以被整除,即係

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

由上可得推理:

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

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

證明:

利用歐幾理得推論,或者

再利用多一次,得出或者

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

歐幾理得證明[編輯]

存在無限質數。

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

假設係一個質數。

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

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

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

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

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

睇埋[編輯]