質數

質數，又叫素數，係個大過 1 嘅自然數，除咗自己同 1 之外，無其他數可以將佢整除。英文入面叫質數做prime number或者prime。

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

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

質數有無限個，公元前300年左右，歐幾理德證明過呢點。頭三十個質數係2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97、101、103、107、109同埋113。

定義 
假設  係一個整數。如果  只有  同埋  係佢嘅因數，咁  就係一個質數。唔係嘅話， 就係一個合成數。 同埋  就質數、合成數兩者都唔係。

搵法

搵質數最簡單係用愛氏篩，即係先將第一個質數嘅倍數篩走，跟住將下一個質數嘅倍數篩走，如此類推。

歐幾理得推論 
歐幾理得推論

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

證明：

假設唔可以被整除，即係。

因為，利用相對質數性質，得出。

由上可得推理：

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

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

證明：

利用歐幾理得推論，或者。

再利用多一次，得出或者。

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

歐幾理得證明
存在無限質數。

證明： 假設得咁多個質數，叫，而家考慮一個整數。

假設係一個質數。

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

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

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

商餘
 質數分解
 質數定理
 相對質數

數論